2
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ what is a top? a vertex? $\endgroup$ – Jorge Fernández Hidalgo Dec 13 '16 at 21:16
  • 2
    $\begingroup$ It is a peculiar term "top" given that the word vertex is also used in the body of the Question. $\endgroup$ – hardmath Dec 13 '16 at 21:19
  • 1
    $\begingroup$ I'm fine with it (though I would have used red and blue as colours ;) ) $\endgroup$ – Hagen von Eitzen Dec 13 '16 at 21:20
  • $\begingroup$ Yes top is vertex, sorry translation error, I fixed it. $\endgroup$ – user370967 Dec 13 '16 at 21:22
  • 1
    $\begingroup$ 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. $\endgroup$ – A. Van Antwerpen Dec 16 '16 at 7:13
0
$\begingroup$

Yes, this solution is perfectly fine. Notice that it can be strengthened to a graph in which every vertex has even degree, and the number of edges in each component is even. ( You can color the edges so that half of the edges of every vertex have one color and the other half has the other color).

$\endgroup$

Your Answer

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