CombinatoricsDifficulty 8.3ShortlistProve itHong Kong
There are n vertices on a plane. A graph G is formed by connecting every two vertices by exactly one edge, and painting all edges, each in one colour, chosen from k given colours.
a. For n=6 and k=3, show that it is possible to paint the edges so that the graph contains no closed circuit painted in one colour only.
b. Prove that for every positive integral value of k (i.e. number of colours allowed), if the number of vertices n≥2k+1, then it is always possible to find a mono-coloured closed circuit in G.
Solution
a. We can colour the edges as shown. Since the subgraph formed by edges of the same colour connects all 6 vertices but there are only 5 edges, it is a tree and hence has no closed circuit.
b. There are (2n)≥2n(n−1) edges in total. By the pigeonhole principle, there are 2kn(n−1) edges which are of the same colour. Consider the subgraph formed by these edges. The number of vertices is at most n. Since 2kn(n−1)≥2kn(2k+1−1)=n, the number of edges of this subgraph is at least the number of vertices. Thus, there must be a closed circuit. This gives a monochromatic closed circuit in G.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.
Source: MathNet,
licensed CC-BY-4.0.
Statement reproduced verbatim; metadata (topic, difficulty) added by this project.