Graph Theory – Prove the Petersen Graph Does Not Have Edge Chromatic Number 3

coloringgraph theory

Explain why the Petersen graph cannot have its edges coloured with exactly 3 colours so that adjacent edges receive different colours.
I know that this is true by looking at the graph, but I'm having trouble coming up with a proof for it and I haven't been able to find one that I understand online.

Any help or insights for how to prove this would be greatly appreciated! Thanks.

Best Answer

There is a really beautiful proof here: http://www.sciencedirect.com/science/article/pii/S0012365X03001389

picture from the linked proof

I will rephrase it a bit:

  • we assume there is a 3-coloring.
  • every vertex has degree $3$, so each color must appear at each vertex.
  • Given the representation of the graph with a pentagon on the outside and a pentagram on the inside.
  • We look at one of the outer edges, call its color $A$ and its vertices $u$ and $v$.
  • We call the neighbor of $u$ on the pentagram $x$. $ux$ can't have color $A$, so one of the other two edges of $x$ has to have color $A$. Both of them are on the pentagram.
  • We call the neighbor of $v$ on the pentagram $y$. $vy$ can't have color $A$, so one of the other two edges of $y$ has to have color $A$. Both of them are on the pentagram.
  • Since $x$ and $y$ don't share an edge, there must be different 2 edges on the pentagram that have color $A$.
  • Since a pentagon can't have a 2-coloring we know that all 3 colors appear on the pentagon. Since we have chosen $A$ arbitrary, we can deduce that each of the edge colors appears twice in the pentagon.
  • The pentagon has only 5 edges, this is a contradiction.
Related Question