Suppose we 2-colour the edges of the complete graph $\displaystyle K_n$. Show that there are two monochromatic paths $\displaystyle P_1$ and $\displaystyle P_2$ such that $\displaystyle V(P_1) \cup V(P_2) = V(K_n)$.

Printable View

- Nov 28th 2010, 11:52 PMBoysilverEdge colouring in K_n
Suppose we 2-colour the edges of the complete graph $\displaystyle K_n$. Show that there are two monochromatic paths $\displaystyle P_1$ and $\displaystyle P_2$ such that $\displaystyle V(P_1) \cup V(P_2) = V(K_n)$.