2
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.
$\endgroup$
1

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.