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!

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

Your answer is right, but you can see it more easily by just forgetting the rest of colors. You already proved that there is a color where you have at least 22 edges

Now take any graph with 20 vertices and (at least) 22 edges, suppose it has no closed loops (so it's planar), then by Euler's theorem (faces + vertices = edges + 2) the number of faces is at least 4. So it has closed loops.

  • $\begingroup$ (by the same Euler's theorem you get that the max number of edges you can have without loops is 19) $\endgroup$ – rewritten Feb 15 '15 at 18:20
  • $\begingroup$ I'm ashamed to admit I forgot this theorem. Thanks for a BEAUTIFUL answer! $\endgroup$ – Galc127 Feb 15 '15 at 18:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.