41
$\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$
0
64
$\begingroup$

One direction is very easy: if $G$ is bipartite with vertex sets $V_1$ and $V_2$, every step along 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$
19
  • 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
6
$\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$
2
  • $\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
5
$\begingroup$

The following is an expanded version of Brian's answer. Brian's answer is almost perfect, except that there may be a gap between "if G had any edge between two red vertices or between two blue vertices" and "it would have an odd cycle", which is not that obvious, at least to me(since we can only conclude that there exists a closed walk of odd numbers of edges). We first prove a lemma stating that if there is an odd closed walk in a graph, then there is an odd closed cycle.

Lemma 1 If there is an odd closed walk in a graph, then there is an odd closed cycyle.

Proof$\;$ We induct on the number of edges $k$ of the odd closed walk. The base case $k=1$, when the closed walk is a loop, holds trivially. Assume that, for some positive integer $r > 1$, Lemma 1 is true for all odd numbers $k\le2r-1$. Let $W=(w_1, \dots, w_{2r+1}, w_1)$ be a closed walk of $2r+1$ edges. If all vertices in $W$ is different except for $w_1$, then we have a cycle of length $2r+1$. If there exists two identical vertices $w_i=w_j$ for $1<i<j\le 2r+1$, then $W$ can be written as $(w_1, \dots,w_i, \dots, w_j,\dots, w_1)$. Thus, we now have two closed walks $W_1=(w_i,w_{i+1} \dots, w_j)$ and $(w_j,w_{j+1} \dots, w_i)$. The summation of the length of $W_1$ and $W_2$ equals to the length of $W$. Since $W$ is of odd length, one of $W_1$ and $W_2$ must be of odd length $\le 2r-1$. By our assumption, there must be a an odd cycle in $W_1$ or $W_2$, and thus in $W$, which completes our induction. $\square$

Theorem 1 If there is no odd cycles in a graph, then the graph is bipartite.

Proof$\;$ Suppose there is no odd cycles in graph $G=(V,E)$. It is also assumed that, without loss of generality, $G$ is connected. Then $V$ can be partitioned into $(A,B)$, where $$A=\{v\in V|\text{the shortest path between $v$ and $v_0$ is of even length}\}$$ $$B=\{v\in V|\text{the shortest path between $v$ and $v_0$ is of odd length}\}$$ Next we prove that there is no edge between any two vertices in $A$ or $B$. Suppose for contradiction that there exists an edge $(x,y)\in E$ such that $x,y \in A$ or $x,y \in B$ . Then the shortest path from $x$ to $v_0$, the shortest path from $y$ to $v_0$, together with edge $(x,y)$, form a closed walk: $(v_0, \dots,x,y, \dots,v_0)$, which is of odd length. By lemma 1, $G$ contains an odd cycle, which is a contradiction. Therefore, $G$ is a bipartite graph between $A$ and $B$ $\square$

$\endgroup$
1
  • $\begingroup$ Is it not sufficient to note that two vertices $u,w$ in the same set of the bipartition cannot share an edge as $d(v_0,u) = d(v_0,w) \pm 1$?. Say $u$ is closer to $v_0$ than $w$. Then one shortest path from $v$ to $w$ is the one passing through $w$. But then the distances to $w$ and $u$ have different parity and so they aren't in the same set. $\endgroup$ – PhysMath May 4 '20 at 4:11
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$
1
  • $\begingroup$ The handshaking Lemma is even simpler $\endgroup$ – SK19 May 8 '19 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.