0
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ Hint: Draw examples of 2-edge-colourable graphs. $\endgroup$
    – Jukka Suomela
    Commented Oct 3, 2014 at 17:53

2 Answers 2

Reset to default
1
$\begingroup$

Hint: 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.

Improve this answer
$\endgroup$
0
$\begingroup$

Bipartite is the same as two colorable.

To show that your graph is two colorable you just need to show that once you color the vertices there are no edges going between two vertices with the same color. Should be easy to show based on the definition of your graph.

Improve this answer
$\endgroup$
3
  • $\begingroup$ How do you color the vertices? $\endgroup$
    – Yuval Filmus
    Commented Oct 3, 2014 at 17:43
  • $\begingroup$ Color one set red and the other one blue. $\endgroup$
    – Aaron
    Commented Oct 3, 2014 at 17:56
  • 1
    $\begingroup$ Which ones do you color which color? Per the question, it is the edges which are partitioned into two groups, not the vertices ("if the edges of an undirected graph $G$ can be grouped into two sets..."). $\endgroup$
    – Yuval Filmus
    Commented Oct 3, 2014 at 17:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.