# Graph theory: Colour edges

Prove: Let G be a simple graph where every vertex has degree 4. Show that you can color the edges in 2 colors such that every vertex is located on 2 edges of one color and 2 edges of the other color.

Proof: We know that there is a Euler cyclus in every connected component (as every vertex has degree 4). Choose a vertex of this Euler cyclus in every component and follow the cyclus. Color the first edge that you encounter in blue, the next one in green, then the next one in blue, ... Now, let's look at what happens at a random vertex v. The Euler cyclus has entered this vertex via for example a blue edge, thus leaves the top via a green edge. We know that the Euler cyclus will come again through v, and if it comes in v via a green vertex, then it leaves via a blue vertex or vice versa. So, every vertex will be located on both 2 blue and 2 green edges, and this for every top in every component. QED

Could someone verify whether this proof is correct?

• what is a top? a vertex? – Jorge Fernández Hidalgo Dec 13 '16 at 21:16
• It is a peculiar term "top" given that the word vertex is also used in the body of the Question. – hardmath Dec 13 '16 at 21:19
• I'm fine with it (though I would have used red and blue as colours ;) ) – Hagen von Eitzen Dec 13 '16 at 21:20
• Yes top is vertex, sorry translation error, I fixed it. – user370967 Dec 13 '16 at 21:22
• Your solution is great. However you need to include an argument To show why your coloring scheme works on the point that you've started in. As Jorge indirectly pointed out, this is connected to the fact you have an even number of edges in every component. – A. Van Antwerpen Dec 16 '16 at 7:13