1
$\begingroup$

I was asked to prove that a graph can be colored in two colors if and only if the graph does not contain a circle with an odd number of edges. I'd really appreciate some help on this one. Thank you!!!

reminder: graph coloring means: labeling of the graph’s vertices with colors such that no two vertices sharing the same edge have the same color

$\endgroup$
  • $\begingroup$ What did you try? $\endgroup$ – Casteels Feb 17 '17 at 19:11
  • $\begingroup$ I tried proving it with induction but sort-of failed $\endgroup$ – Lola Feb 17 '17 at 19:12
  • $\begingroup$ "Circle" in your post should be "cycle", a term in graph theory for a path that ends at the same vertex it begins. $\endgroup$ – hardmath Feb 17 '17 at 20:48
1
$\begingroup$

Any cycle starts from a blue node and ends at the same blue node. If the graph is 2-colorable the the cycle is an alternating sequence of red and blue node that begins and ends with the same color, therefore the cycle... has an event number of nodes and an even number of arcs.

Btw, such a graph will be bipartite, blue nodes on the left and red ones on the right. Or the other way around :^).

$\endgroup$
  • 1
    $\begingroup$ Thank you! I did figure that out but I'm asked to prove that formally..is this a formal answer?:( $\endgroup$ – Lola Feb 17 '17 at 19:20
  • 1
    $\begingroup$ @ lola Yes, it is. You could nitpick giving names to the arcs and nodes but that would not bring much to the argument. $\endgroup$ – A.G. Feb 17 '17 at 19:31

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.