Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How can we prove that a graph is bipartite if and only if all of its cycles have even order? Also, does this theorem have a common name? I found it in a maths Olympiad toolbox.

share|improve this question
add comment

2 Answers

up vote 9 down vote accepted

One direction is very easy: if $G$ is bipartite with vertex sets $V_1$ and $V_2$, every step alone a walk takes you either from $V_1$ to $V_2$ or from $V_2$ to $V_1$. To end up where you started, therefore, you must take an even number of steps.

Conversely, suppose that every cycle of $G$ is even. Let $v_0$ be any vertex. For each vertex $v$ in the same component $C_0$ as $v_0$ let $d(v)$ be the length of the shortest path from $v_0$ to $v$. Color red every vertex in $C_0$ whose distance from $v_0$ is even, and color the other vertices of $C_0$ blue. Do the same for each component of $G$. Check that if $G$ had any edge between two red vertices or between two vertices, it would have an odd cycle. Thus, $G$ is bipartite, the red vertices and the blue vertices being the two parts.

share|improve this answer
    
genius... thanks a lot Brian! –  Euler Nov 28 '13 at 4:58
    
@Atahualpa: You’re welcome! –  Brian M. Scott Nov 28 '13 at 16:15
add comment

One relatively simple way is to break the if and only if into its two parts:

  • Prove that if a graph $G$ is bipartite then it has no odd cycles, and
  • If $G$ has only even cycles, then you can partition the vertices into two independent sets.

I don't think this is a named theorem, it's too simple.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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