Why is it that if the edges of an undirected graph G can be grouped into two set

Question

Why is it that if the edges of an undirected graph G can be grouped into two sets such that every vertex is incident to at most 1 edge from each set, then the graph is 2-colorable.

The reason that I am guessing this happens is because the graph is bipartite. But I was not sure about this... I was trying to show it was bipartite and then show thus that it was two colorable, but I didn't really know how to start showing it was bipartite. Somebody know of a rigorous way to show this? Or what the intuition for the proof is?

Explanation / Answer

Consider a cycle in your graph. The edge colors must alternate, so the cycle must have even length. A graph is bipartite iff it has no odd cycles.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.