# Prove that the Petersen graph does not have edge chromatic number = 3.

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.

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

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.
• Thanks, that helped a lot! Oct 18, 2017 at 22:40