Question 43
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 \ge 2k+1$, then it is always possible to find a mono-coloured closed circuit in $G$.
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 \ge 2k+1$, then it is always possible to find a mono-coloured closed circuit in $G$.