1
$\begingroup$

The problem is given as follow:

Let G be a connected graph having an even number of edges such that all the degrees are even. Prove that the edges of G can be colored by red and blue in such a way that every vertex has the same number of red and blue edges adjacent to it.

My approach is:

Since all degrees are even, then G is not a tree and contains only cycles. This also implies two cycles cannot share a common edge, otherwise one vertex has odd degree. G has even number edges indicates it has even number of cycles which share common vertices. Therefore, G can be colored by red and blue in such a way that every vertex has the same number of red and blue edges adjacent to it.

I don't know if I miss something needs to be clarify in this proof...


My new approach:

G contains a Eulerian circuit because all the degrees are even. Traversing the circuit from a vertex u and coloring the edges blue, red, blue, red....as a sequence. Because G has even number of edges, it has even number of blue and red edges; hence, the color of first edge starting from vertex u is different from the last edge goes back to starting point. Therefore, QED

$\endgroup$
  • 1
    $\begingroup$ "$G$ contains only cycles" It is not clear what exactly you mean by this. "Two cycles cannot share a common edge." As a counterexample to both claims (depending on what exactly you mean by the first), consider the graph $K_5$. The graph is indeed connected, has $\binom{5}{2}=10$ edges, is $4$-regular and thus has no vertices of odd degree. However, there exist cycles within it which share edges (e.g. any five-cycle and any three-cycle). $\endgroup$ – JMoravitz Aug 24 '16 at 19:31
  • 1
    $\begingroup$ It may be worth looking into the concept of Eulerian Circuits. Since $G$ is connected and has all degrees even, it follows immediately that such an Eulerian Circuit exists. Can you manipulate that circuit to give you what you want? (Remember that there is usually a reason for all hypotheses. The fact that there are an even number of edges is important) $\endgroup$ – JMoravitz Aug 24 '16 at 19:36
  • $\begingroup$ @JMoravitz thanks for the hint. I'm trying to solve it $\endgroup$ – Pay C. Aug 24 '16 at 20:02
  • $\begingroup$ Your edit includes an attempt at a correct proof. There are a few missing details. "G contains an Eulerian circuit because all the degrees are even and it is connected..." The and is connected is necessary to mention in the body of the proof. You successfully showed that the first edge is a different color than the last edge. You have not yet explained why each vertex individually has the same number of each color edge. Note here that with the exception of the vertex $u$ over the course of traveling around the circuit...[continued...] $\endgroup$ – JMoravitz Aug 25 '16 at 19:51
  • $\begingroup$ [...continued] each time we encounter a vertex it will be both approached and left in immediate succession. Those edges will be different colors, so by each time we have left a vertex, the net change to the difference between the number of red and blue edges for that vertex is unchanged. This argument does not work for the vertex $u$, but a similar argument shows that if you temporarily ignore the first and last edge, you will have a difference of zero. Adding back in the first and last edge it remains zero. Thus all vertices have same number of red and blue edges. $\endgroup$ – JMoravitz Aug 25 '16 at 19:54
3
$\begingroup$

Since it was quite some time ago that I gave a hint in the comments above and the OP has not returned to say that he has figured it out and no other answer has been posted, I will give an extended hint (practically a full solution):


Depending on strictness and definitions, one might also want to concern yourself with the case that $G$ has exactly one vertex (or even exactly zero vertices). There is exactly one graph with exactly one vertex, and it has zero edges and can trivially be seen to satisfy all of the conditions. It is common to see graph theory problems specify that we are interested only in proving results for graphs with at least $n\geq 2$ vertices since the one-vertex graph is so dull and uninteresting.

As $G$ is connected and has every vertex with even degree, there exists an Eulerian circuit (a walk which possibly reuses vertices that starts and ends in the same place which uses every edge exactly once).

Take any such Eulerian circuit with starting and ending point $x$ (where $x$ is a vertex of $G$) and alternately color the edges along the circuit red and blue.

It remains to show the following two things:

  • Why does every vertex other than $x$ have as many red edges as blue edges?

  • Why does $x$ have as many red edges as blue edges?

Why is the last edge in the circuit a different color than the first edge in the circuit? (Have we used all of the hypotheses yet in our proof?)

$~$

Would $x$ have had as many red edges as blue edges if the number of edges in the graph total was in fact odd? What are the colors of the first and last edge in the circuit in that case?

$\endgroup$
  • $\begingroup$ Thanks, I sort of figured it out, but I'm not sure if it's correct so I didn't post it here :( it may mislead fellows.... $\endgroup$ – Pay C. Aug 25 '16 at 10:35

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.