# How to prove that A graph is bipartite if and only if it contains no odd cycles using mathematical induction and contradiction

How can we prove König's Theorem using both mathematical induction and contradiction?

I got the idea of making the assumption in the beginning that a bipartite graph can have an odd cycle and prove that it's impossible to do so for $K= 3$, $K = n$ but how to apply it for $K = n+1$.

It's easy to prove the result if we know the following:

1. That any odd cycle cannot possibly be bipartite
2. Any subgraph of a bipartite graph is also bipartite

Proof: Suppose a bipartite graph $G$ contained a odd cycle $C$. Since $C$ is a subgraph of $G$, then it is also bipartite. However, $C$, which is an odd cycle, cannot possibly be bipartite, thus, we have a contradiction. Thus, $G$ has no odd cycle.

The proof of (2) shouldn't be too difficult, but we can prove (1) using induction.

Proof: Consider an odd cycle $C$ of length $2n+1$ where $n\in \mathbb{N}$ and suppose by means of contradiction that is was bipartite. Then there exists a partition of the vertices into sets $U$ and $V$ such that none of the vertices in $U$ are adjacent to one another and none of the vertices in $V$ are adjacent to one another. Suppose the vertices of $C$ are labeled as $v_1, v_2, \dots, v_{2n+1}$ where $(v_i, v_{i+1}) \in E(C)$ for $i=1,\dots,n-1$ and $(v_{2k+1},v_1) \in E(C)$ where $E(G)$ represents the edge set of a graph $G$. Without loss of generality, suppose $v_1 \in U$. We will show that for all natural numbers $m \leq n$ that $v_{2m+1} \in U$.

The base case for $m=0$ is trivial since we know $v_{2(0)+1} = v_1 \in U$.

Suppose the statement is true for $m=k$ where $k<n$, we now wish to show that it is true for $m = k+1 \leq n$. Thus, we have that $v_{2k+1} \in U$ and we wish to show that $v_{2(k+1)+1} = v_{2k+3} \in U$. Notice that $v_{2k+1}$ is adjacent to $v_{2k+2}$ and $v_{2k+1} \in U$, and thus $v_{2k+2} \in V$ (due to the partitions not allowing adjacent vertices within them). Similary, $v_{2k+2}$ is adjacent to $v_{2k+3}$ and $v_{2k+2} \in V$, thus $v_{2k+3} \in U$. Thus showing the result.

From our induction, we have that $v_1 \in U$ and $v_{2n+1} \in U$. However, notice that $v_1$ and $v_{2n+1}$ are adjacent and thus they cannot both be in $U$, thus, we have a contradiction. Thus, an odd cycle cannot be bipartite.

Notice in this proof, the induction wasn't on the number of vertices in the cycle, but rather, the labeling of the vertices within a cycle. Also, my proof is a bit of the opposite of what you're asking for since I have a proof by induction as part of my proof by contradiction whereas it seems you are looking for a proof by contradiction within a proof by induction. Anyways, hope this was of some help!