8
Part of 2016 Tuymaada Olympiad
Problems(2)
Graph problem
Source: tuymaada 2016. seniors P8
7/22/2016
A connected graph is given. Prove that its vertices can be coloured
blue and green and some of its edges marked so that every two vertices
are connected by a path of marked edges, every marked edge connects
two vertices of different colour and no two green vertices are connected
by an edge of the original graph.
combinatoricsgraph theory
Nice problem
Source: Tuymaada 2016
6/28/2017
The flights map of air company presents several cities. Some cities are connected by a direct (two way) flight, the total number of flights is m. One must choose two non-intersecting groups of r cities each so that every city of the first group is connected by a flight with every city of the second group. Prove that number of possible choices does not exceed .
combinatoricsgraph theory