# Test question regarding graph theory - please check my work

I had a test today and there was a question regarding graph theory. I want some feedback on my solution.

Let $K_{20}$ be a complete graph with $20$ vertices. The edges of the graph are colored in $9$ different colors. Show that there is a circle which all of its edges are colored with the same color.

My try: First of all, the graph is complete, hence there are $\displaystyle {20 \choose 2}=190$ edges. There are $9$ different colors, hence by the pigeonhole principal there are at least $\displaystyle \lceil{\frac{190}{9}\rceil}=22$ edges of the same color. Now, every vertex is connceted by $19$ edges, hence by the pigeonhole principal there are at least $\displaystyle \lceil{\frac{22}{19}\rceil}=2$ edges that are connected to the same vertex and there are with the same color. By the pigeonhole principal we also know that there are at least $\displaystyle \lceil \frac{22}{20}\rceil=2$ vertices that the same edges are connected to them. The graph is complete, thus these two vertices has two commom neighbors, and if we connect all of these 4 vertices we get a circle with length 4 of which all edges are colored in the same color.

Is that good? thanks!

• I wanted to write $\displaystyle {20 \choose 9}$ Feb 15 '15 at 18:03
• @MarkG K(n) has $n\choose{2}$ edges. Feb 15 '15 at 18:06