27
$\begingroup$

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.

$\endgroup$
45
$\begingroup$

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 blue vertices, it would have an odd cycle. Thus, $G$ is bipartite, the red vertices and the blue vertices being the two parts.

$\endgroup$
  • 1
    $\begingroup$ @YOUSEFY: That’s the direction that I proved in the first paragraph. And I gave direct proofs for both directions. $\endgroup$ – Brian M. Scott Oct 19 '16 at 9:43
  • 2
    $\begingroup$ @YOUSEFY: No, I mean the first paragraph. What you proved in your comment is that if $G$ has an odd cycle, then $G$ is not bipartite, which is the contrapositive of (and logically equivalent to) the statement that if $G$ is bipartite, then it has no odd cycle. What I proved in the second paragraph is that if $G$ does not have an odd cycle, then $G$ is bipartite. This is the converse of what you proved. $\endgroup$ – Brian M. Scott Oct 19 '16 at 15:34
  • 1
    $\begingroup$ @sourav: If you start at a vertex in $V_1$ and take a walk of length $3$, say, your first step goes to a vertex in $V_2$, your second to a vertex in $V_1$, and your third to a vertex in $V_2$; since you started in $V_1$ and are now in $V_2$, you can’t possibly have returned to your starting vertex. The same thing happens for any odd number of steps. $\endgroup$ – Brian M. Scott Nov 1 '16 at 16:31
  • 1
    $\begingroup$ @sourav: You’re welcome. $\endgroup$ – Brian M. Scott Nov 1 '16 at 16:37
  • 1
    $\begingroup$ @sourav: No, the graph is not bipartite. Being bipartite has nothing to do with how many components the graph has. A graph is bipartite if the vertices can be partitioned into two sets, say $V_1$ and $V_2$, such that every edge is between a vertex in $V_1$ and a vertex in $V_2$, i.e., so that there are no edges between vertices in $V_1$ and no edges between vertices in $V_2$. $\endgroup$ – Brian M. Scott Nov 1 '16 at 18:45
2
$\begingroup$

does this theorem have a common name?

It is sometimes called König's Theorem (1936), for example in lecture notes here.


However, this name is ambiguous.

$\endgroup$
  • $\begingroup$ I expanded your answer a bit, as it drew some low-quality flags. $\endgroup$ – user147263 Jul 1 '15 at 17:45
  • $\begingroup$ I don't agree with you. in the textbook of Diestel, he mentiond König's theorem in page 30, and he mentiond the question of this site in page 14. he didn't say at all any similiarities between the two. Also, König's talks about general case of r-paritite so if what you're saying is true, then the theorem is just a special case of general case. Right now, I don't have any name for it except it is a proposition (means something that mathematicains do find it interesting but it doesn't come becasue they're thinking on it so much) $\endgroup$ – YOUSEFY Oct 18 '16 at 17:15
0
$\begingroup$

(By contradiction) (->) Suppose n is odd. Let X={ui such that i is odd} and Y={ui such that i is even} as the bipartition formed in the graph. Consider cycle C=u1 u2 u3 u4...un u1 as the cycle in G. If u1 is odd, un can not be odd because there will be no bipartite formed. Therefore, n should be even.

$\endgroup$
-1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The handshaking Lemma is even simpler $\endgroup$ – SK19 May 8 at 1:11

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.