There is a regular graph. Degree of each vertex is four. It needs to prove that edges of the graph can be colored in two colors so that each vertex is incident to two edges of the same color and the two edges of a different color. I do not know how to prove it. I think this task is equal to the task of removing the edges of the graph so as to obtain a regular graph in which each vertex has exactly two edges. Thank you in advance.


I'm assuming that the graph is undirected.


  • If the graph has multiple connected components, you can color them independently.
  • If the degree of all the vertices is $4$, then there is an Eulerian cycle in the graph/component.
  • Color the edges in the cycle in alternating colors, e.g. every second edge one color and the rest the other color.

I hope this helps $\ddot\smile$


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.