Maths Olympiad Prep

Library / /25 of 28

Combinatorics Difficulty 8.3 Shortlist Prove it Hong Kong

There are nn vertices on a plane. A graph GG is formed by connecting every two vertices by exactly one edge, and painting all edges, each in one colour, chosen from kk given colours.

a. For n=6n = 6 and k=3k = 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 kk (i.e. number of colours allowed), if the number of vertices n2k+1n \ge 2k+1, then it is always possible to find a mono-coloured closed circuit in GG.

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.

Figure 1

b. There are (n2)n(n1)2\binom{n}{2} \ge \frac{n(n-1)}{2} edges in total. By the pigeonhole principle, there are n(n1)2k\frac{n(n-1)}{2k} edges which are of the same colour. Consider the subgraph formed by these edges. The number of vertices is at most nn. Since
n(n1)2kn(2k+11)2k=n, \frac{n(n-1)}{2k} \ge \frac{n(2k+1-1)}{2k} = 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 GG.

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.