Question about proof for bipartite containing no odd cycles

1k Views Asked by At

I red the proof from here https://proofwiki.org/wiki/Graph_is_Bipartite_iff_No_Odd_Cycles

Sufficient Condition

Let $G=(V,E)$ be bipartite.

So, let $V=A∪B$ such that $A∩B=∅$ and that all edges $e∈E$ are such that $e$ is of the form $\{a,b\}$ where $a∈A$ and $b∈B$.

(This is the definition of a bipartite graph.)

Suppose $G$ has (at least) one odd cycle $C$.

Let the length of $C$ be $n$.

Let $C=(v_1,v_2,\cdots,v_n,v_1)$.

WLOG, let $v_1∈A$. It follows that $v_2∈B$ and hence $v_3∈A$, and so on.

Hence we see that $∀k∈\{1,2,\cdots,n\}$, we have:

$v_k∈\{A:B:k$ odd $k$ even

But as $n$ is odd, $v_n∈A$.

But $v_1∈A$, and $v_nv_1∈C_n$.

So $v_nv_1∈E$ which contradicts the assumption that $G$ is bipartite.

Hence if $G$ is bipartite, it has no odd cycles.

I don't understand how "So $v_nv_1∈E$ which contradicts the assumption that G is bipartite." is it because both $v_n$ and $v_1$ are in the set $A$ so that's a contradiction of $A$ and $B$ being disjoint?

1

There are 1 best solutions below

2
On

No. We have an edge $\{v_n, v_1\} \in E$ where $v_n, v_1 \in A$. This contradicts the fact that $G$ is bipartite, and so each edge should have been of the form $\{a, b\}$ with $a \in A$ and $b \in B$. The indicated edge does not have this form, which is a contradiction.