[proofplan] We prove both directions. The forward direction is a direct parity argument: if $G$ were bipartite and contained an odd cycle, two-colouring the cycle would alternate parts along its edges and force the start and end of the cycle to lie in different parts — contradicting closure. The reverse direction is constructive: assuming $G$ is connected (the general case follows by taking components), we fix a root $x_0$ and define the bipartition by the parity of the graph-distance to $x_0$. The only way this could fail is if two vertices in the same part were joined by an edge; concatenating their shortest paths to $x_0$ through this edge yields a closed walk of odd length, which contains an odd cycle by the [Odd Circuits Contain Odd Cycles](/theorems/2012) theorem, contradicting the hypothesis. [/proofplan] [step:Prove the forward direction by contraposition: an odd cycle obstructs bipartiteness] We prove the contrapositive: if $G$ contains an odd cycle, then $G$ is not bipartite. Suppose $G$ contains an odd cycle $C: x_1, x_2, \ldots, x_{2k+1}, x_1$ of length $2k + 1$ for some $k \ge 1$. Assume for contradiction that $G$ is bipartite with bipartition $V(G) = A \sqcup B$, i.e., every edge of $G$ has one endpoint in $A$ and one in $B$. Without loss of generality, $x_1 \in A$. Since $\{x_1, x_2\}$ is an edge of $G$, the bipartition forces $x_2 \in B$. Since $\{x_2, x_3\}$ is an edge, $x_3 \in A$. By induction on $i$, for each $1 \le i \le 2k + 1$, \begin{align*} x_i &\in A \quad \text{if } i \text{ is odd}, \\ x_i &\in B \quad \text{if } i \text{ is even}. \end{align*} In particular, $x_{2k+1} \in A$ since $2k + 1$ is odd. But $\{x_{2k+1}, x_1\}$ is an edge of $C$ (and hence of $G$), and both endpoints lie in $A$ — contradicting the bipartition. Hence $G$ is not bipartite. [guided] The forward direction is really a statement about $2$-colourability: a graph is bipartite if and only if its vertices can be properly $2$-coloured (adjacent vertices receive different colours). Along any cycle $x_1, x_2, \ldots, x_\ell, x_1$, a proper $2$-colouring must alternate colours at each step, so $x_i$ and $x_{i+1}$ always differ. After traversing the full cycle we return to $x_1$, and the colour of $x_1$ must match the colour we arrive at after $\ell$ alternations. Alternation $\ell$ times flips the colour $\ell$ times; for the final colour to match the starting colour, $\ell$ must be even. An odd cycle breaks this, which is exactly the contradiction above. The induction on $i$ is worth stating cleanly. Base case: $x_1 \in A$ by assumption, and $1$ is odd, matching the rule. Inductive step: suppose $x_i$ lies in the part predicted by the parity of $i$. The edge $\{x_i, x_{i+1}\}$ forces $x_{i+1}$ to lie in the opposite part, and the parity of $i+1$ flips, so $x_{i+1}$ also matches the rule. This covers all of $x_1, \ldots, x_{2k+1}$. The contradiction comes from the **closing** edge $\{x_{2k+1}, x_1\}$, which is the only edge not handled by the alternation rule: both endpoints are in $A$. [/guided] [/step] [step:Reduce the reverse direction to the connected case] For the reverse direction, assume $G$ contains no odd cycle. We must show $G$ is bipartite. Decompose $G$ into its connected components $G_1, G_2, \ldots, G_m$ (with $V(G) = \bigsqcup_{r=1}^m V(G_r)$ and every edge contained in some $V(G_r)$). If each $G_r$ admits a bipartition $V(G_r) = A_r \sqcup B_r$, then setting \begin{align*} A := \bigsqcup_{r=1}^m A_r, \qquad B := \bigsqcup_{r=1}^m B_r \end{align*} gives a bipartition of $G$: every edge of $G$ lies in some $G_r$ and hence has one endpoint in $A_r \subseteq A$ and the other in $B_r \subseteq B$. Since no $G_r$ contains an odd cycle (any cycle in $G_r$ is a cycle in $G$), it suffices to prove the result under the additional assumption that $G$ is connected. For the remainder of the proof, assume $G$ is connected. [/step] [step:Define the bipartition by parity of distance to a fixed root] Since $G$ is connected, the graph-distance $d: V(G) \times V(G) \to \mathbb{Z}_{\ge 0}$ (the length of a shortest path) is finite on all pairs. Fix a root vertex $x_0 \in V(G)$ and define \begin{align*} V_0 &:= \{x \in V(G) : d(x, x_0) \text{ is even}\}, \\ V_1 &:= \{x \in V(G) : d(x, x_0) \text{ is odd}\}. \end{align*} Since every non-negative integer is either even or odd but not both, $V_0 \cap V_1 = \varnothing$ and $V_0 \cup V_1 = V(G)$. In particular $x_0 \in V_0$ since $d(x_0, x_0) = 0$. [guided] The construction is canonical: pick any root and split vertices by the parity of their graph-distance to the root. The choice of root only affects which part a vertex lies in; it does not affect whether the graph is bipartite. One might worry: what if $d(x, x_0)$ is undefined for some $x$? It is not — connectedness guarantees a path from $x_0$ to any $x$, and the length of a shortest such path is a well-defined non-negative integer. This is why we reduced to the connected case. [/guided] [/step] [step:Show that no edge joins two vertices of the same part] We must verify that every edge $\{u, v\}$ of $G$ has one endpoint in $V_0$ and the other in $V_1$. Suppose for contradiction that there exist an edge $\{u, v\}$ with both $u, v \in V_i$ for some $i \in \{0, 1\}$. Then $d(x_0, u)$ and $d(x_0, v)$ have the same parity. Choose a shortest path $P_u$ from $x_0$ to $u$ of length $d(x_0, u)$, and a shortest path $P_v$ from $x_0$ to $v$ of length $d(x_0, v)$. Concatenating $P_u$, the edge $\{u, v\}$, and the reverse of $P_v$ produces a closed walk \begin{align*} W: x_0 \to u \to v \to x_0 \end{align*} of length \begin{align*} |W| = d(x_0, u) + 1 + d(x_0, v). \end{align*} Since $d(x_0, u)$ and $d(x_0, v)$ have the same parity, their sum is even, and $|W| = \text{even} + 1$ is odd. Also $|W| \ge 1$ (the edge $\{u, v\}$ contributes at least $1$), so $W$ is a non-trivial odd closed walk, i.e., an odd circuit in $G$. [guided] Let us unpack why $W$ is a valid circuit rather than merely a walk. A **circuit** here means a closed walk — a sequence of vertices $x_0 = w_0, w_1, \ldots, w_r = x_0$ with each $\{w_{j-1}, w_j\}$ an edge of $G$. The concatenation $P_u \cdot \{u, v\} \cdot P_v^{-1}$ starts at $x_0$, ends at $x_0$, and every consecutive pair is an edge of $G$, so it is a circuit. We make no claim that it is a cycle (no repetition of vertices) — indeed, the shortest paths $P_u$ and $P_v$ may share vertices, and that is precisely the source of subtlety that the next step resolves. The parity count is the heart of the argument: the edge $\{u, v\}$ contributes a single $+1$ to the length, which flips the parity of $d(x_0, u) + d(x_0, v)$. If $u$ and $v$ have distances of the same parity to $x_0$, the sum is even, so the total length $d(x_0, u) + 1 + d(x_0, v)$ is odd. This is why the existence of a monochromatic edge (relative to the parity bipartition) forces an odd closed walk. [/guided] [/step] [step:Derive a contradiction by extracting an odd cycle from the odd circuit] The circuit $W$ has odd length, so by the [Odd Circuits Contain Odd Cycles](/theorems/2012) theorem, $W$ contains an odd cycle $C$ as a subgraph. Since the edges of $W$ are edges of $G$, the cycle $C$ is an odd cycle in $G$. This contradicts our hypothesis that $G$ contains no odd cycle. Hence no edge $\{u, v\}$ of $G$ has both endpoints in the same part $V_i$. Consequently every edge of $G$ joins a vertex of $V_0$ to a vertex of $V_1$, which is exactly the definition of $V(G) = V_0 \sqcup V_1$ being a bipartition. Therefore $G$ is bipartite, completing the reverse direction and the proof. [guided] We invoked [Odd Circuits Contain Odd Cycles](/theorems/2012) precisely because $W$ is only guaranteed to be an odd circuit, not an odd cycle. The distinction matters: the concatenation $P_u \cdot \{u,v\} \cdot P_v^{-1}$ might revisit vertices (the shortest paths $P_u, P_v$ could pass through a common vertex before reaching $u, v$). The theorem on odd circuits lets us upgrade this combinatorial artifact — an odd closed walk — to an honest odd cycle, which is the object forbidden by our hypothesis. This is the only place in the proof where the non-bipartite obstruction is invoked, and it is invoked in its sharpest form: the absence of odd **cycles** is parlayed, via the odd-circuits theorem, into the absence of odd **closed walks**, which is what the distance-parity construction actually produces. [/guided] [/step]