Bipartite Graphs and Characterization

Can the vertices of a graph always be split into two camps? The requirement is that every edge crosses between them. This question — deceptively simple — turns out to have a clean, checkable answer. That answer is one of the most useful structural facts in all of graph theory. A graph with this two-camp property is called bipartite. Bipartite graphs sit at the foundation of scheduling problems, matching markets, coloring theory, and even coding theory. The idea matters because bipartiteness is not just a labeling convenience. It is a hidden combinatorial symmetry that forces strong consequences. Bipartite graphs are exactly the 2-colorable graphs. They are exactly the graphs where every cycle has even length. They are also exactly the graphs that admit no odd closed walk. These are three very different-looking conditions. Yet they coincide perfectly, and proving that coincidence is the heart of this article. The big picture is this: many graphs arising from real structures are naturally bipartite. Examples include job-applicant assignments, tasks-and-machines scheduling, chemical bond graphs, and relational databases split into two entity types. Their vertices already come in two kinds, with edges only between kinds. Recognizing when a graph can be arranged this way is the practical problem this article solves. This matters even if the graph is not presented that way. Once we know a graph is bipartite, an entire toolbox becomes available. This includes matchings, König's theorem, and perfect matching algorithms. This article gives the precise definition of a bipartite graph. It builds the visual and combinatorial intuition for why odd cycles are the obstruction. Then it proves the central characterization theorem in full: a graph is bipartite if and only if it contains no cycle of odd length. We verify the proof with concrete numeric examples. We exhibit a counterexample showing why connectivity assumptions must be handled carefully. Finally, we situate the result within the broader landscape of graph coloring and matching theory. We also cover applications across computer science and the sciences.

Key takeaways
  • A graph is bipartite if its vertex set splits into two parts with all edges crossing between them.
  • Bipartiteness is equivalent to having a proper 2-coloring of the vertices.
  • The central fact: a graph is bipartite iff it has no cycle of odd length.
  • The proof of the hard direction uses BFS layering by distance from a fixed vertex.
  • Odd cycles (like the triangle C3C_3 or the 5-cycle C5C_5) are the unique obstructions to bipartiteness.
  • Key idea: the absence of odd cycles is not just necessary but sufficient for a two-part split — checking parity of cycles is a complete test for bipartiteness.

Where this lives today

Bipartite graphs and their odd-cycle test appear constantly across mathematics, computer science, and applied fields. In combinatorial optimization, bipartite graphs model assignment problems — workers to jobs, students to schools, kidneys to recipients — where maximum matchings (foreshadowed by Matchings and Hall's Theorem) find optimal pairings, and the bipartite structure is what makes these problems tractable in polynomial time, unlike general-graph matching. In graph coloring theory (see Graph Coloring and Chromatic Number), bipartite graphs are exactly the graphs with chromatic number at most 2, making the odd-cycle test a fast diagnostic: a single BFS pass, run once per connected component, decides 2-colorability in linear time, whereas testing kk-colorability for k≥3k \geq 3 is NP-hard in general. In coding theory and cryptography, bipartite Tanner graphs represent low-density parity-check (LDPC) codes, connecting bit-nodes to check-nodes; the bipartite structure is essential to efficient belief-propagation decoding algorithms used in modern wireless and storage systems. In database theory and network science, bipartite graphs model relations between two distinct entity types — users and products in recommendation systems, authors and papers in citation networks, or genes and diseases in bioinformatics — and detecting whether an observed interaction graph is genuinely bipartite (or close to it) informs community-detection and projection algorithms. In statistical physics, the Ising model on a bipartite lattice (such as the square lattice, which is bipartite via a checkerboard coloring) has special symmetry properties, including exact solvability results that exploit the two-sublattice structure directly traceable to the absence of odd cycles. Finally, in theoretical computer science, bipartiteness testing is a canonical example of an efficiently decidable graph property, contrasted with harder properties like general chromatic number, and it serves as a building block in algorithms for network flow, stable matching, and scheduling.

Ask the tutor: How does the odd-cycle characterization extend into a proof strategy for König's theorem on matchings and vertex covers in bipartite graphs?

DefinitionBipartite Graph

A graph G=(V,E)G = (V, E) is bipartite if there exists a partition of the vertex set into two disjoint sets V=A∪BV = A \cup B, with A∩B=∅A \cap B = \varnothing, such that every edge e∈Ee \in E has one endpoint in AA and the other endpoint in BB. The pair (A,B)(A, B) is called a bipartition of GG. Equivalently, GG is bipartite if it admits a function c:V→{0,1}c: V \to \{0, 1\} such that c(u)≠c(v)c(u) \neq c(v) for every edge uv∈Euv \in E — that is, a proper 2-coloring of VV. A graph that is not bipartite is called non-bipartite. A graph on nn vertices in which every vertex of AA is adjacent to every vertex of BB is the complete bipartite graph Km,nK_{m,n}, where ∣A∣=m|A| = m, ∣B∣=n|B| = n.

Intuition

Picture the vertices of a graph as people at a party who must be split into two rooms, Room AA and Room BB, with the rule that every pair of friends (an edge) must end up in different rooms. If you can always satisfy this rule no matter how the friendships are arranged, the friendship graph is bipartite. A single triangle of three mutual friends immediately breaks the rule: put the first two in different rooms, but the third friend is tied to both, and there is no room left that avoids putting two friends together. This is the seed of the entire theory — odd cycles are structurally incompatible with a two-room split, while even cycles are perfectly happy with one, since you can alternate rooms all the way around and return to your starting room correctly. The deeper mechanism, and the one the proof exploits, is distance layering. Fix any vertex vv and sort every other vertex by its shortest-path distance to vv: distance 00, distance 11, distance 22, and so on. If the graph is bipartite, then all vertices at even distance from vv must lie in one color class, and all vertices at odd distance must lie in the other — because each step along a shortest path flips the color. The only way this layering can fail to produce a valid bipartition is if some edge connects two vertices at the same distance from vv, and it turns out such an edge exists precisely when there is an odd cycle running through the graph. The picture below shows a 5-cycle, which is not bipartite, laid out by distance from a fixed vertex, with the fatal same-layer edge highlighted.

Figure
BFS layering of the 5-cycle C5C_5 from vertex v0v_0: layers by distance, with the odd "closing" edge shown in red
dist 0 dist 1 dist 2 v0 v1 v4 v2 v3 same-layer edge

Notice in the picture that v2v_2 and v3v_3 are both at distance 22 from v0v_0, yet they are joined by an edge. That single same-layer edge is what forces a color clash and certifies non-bipartiteness — and it is exactly the "extra" edge closing the odd 5-cycle v0v1v2v3v4v0v_0 v_1 v_2 v_3 v_4 v_0.

TheoremKönig's Bipartiteness Characterization

Let G=(V,E)G = (V, E) be a graph (finite, simple, undirected). Then GG is bipartite if and only if GG contains no cycle of odd length.

LemmaNecessity of the odd-cycle condition

If GG is bipartite, then every cycle in GG has even length.

Proof

Technique: direct combinatorial argument on a traversal of the cycle. Suppose GG is bipartite with bipartition (A,B)(A,B), so every edge has one endpoint in AA and one in BB. Let C=v1v2⋯vkv1C = v_1 v_2 \cdots v_k v_1 be a cycle in GG of length kk (so v1,…,vkv_1,\dots,v_k are distinct vertices and vivi+1∈Ev_iv_{i+1}\in E for 1≤i≤k1\le i\le k, indices mod kk). Because each edge vivi+1v_iv_{i+1} crosses between AA and BB, consecutive vertices along the cycle always lie in different parts. Hence, walking along the cycle starting from v1v_1, the sequence of parts alternates: if v1∈Av_1\in A then v2∈Bv_2\in B, v3∈Av_3\in A, v4∈Bv_4 \in B, and in general vi∈Av_i \in A when ii is odd and vi∈Bv_i \in B when ii is even (or the reverse, depending on which part v1v_1 is in — the argument is symmetric). Since the cycle closes up, vkv_k must be adjacent to v1v_1, so vkv_k and v1v_1 lie in different parts. But v1∈Av_1 \in A, so vk∈Bv_k \in B, which by the alternation rule forces kk to be even (only even-indexed vertices lie in BB). Thus every cycle in GG has even length. ■\blacksquare

∎
Proof

Technique: constructive proof via breadth-first-search layering, argued by contradiction on a hypothetical odd cycle. We now prove the converse and harder direction: if GG has no odd cycle, then GG is bipartite. It suffices to prove this for each connected component of GG separately, since a graph is bipartite exactly when every connected component is bipartite (color each component independently using its own bipartition; the choice of which side is "AA" in one component is independent of another, since there are no edges between components to create conflicts). So assume GG is connected and has no odd cycle. Fix an arbitrary vertex v0∈Vv_0 \in V. For each vertex u∈Vu \in V, let d(u)d(u) denote the length of a shortest path from v0v_0 to uu (this is well-defined and finite since GG is connected). Define

A={u∈V:d(u) is even},B={u∈V:d(u) is odd}.A = \{u \in V : d(u) \text{ is even}\}, \qquad B = \{u \in V : d(u) \text{ is odd}\}.

Clearly A∪B=VA \cup B = V and A∩B=∅A \cap B = \varnothing, since every vertex has a well-defined distance to v0v_0 which is either even or odd. We claim (A,B)(A,B) is a valid bipartition, i.e., every edge of GG has one endpoint in AA and one in BB.

Key fact used: for any edge xy∈Exy \in E, the distances satisfy ∣d(x)−d(y)∣≤1|d(x) - d(y)| \leq 1. This holds because if PP is a shortest path from v0v_0 to xx of length d(x)d(x), then appending the edge xyxy gives a walk from v0v_0 to yy of length d(x)+1d(x)+1, so d(y)≤d(x)+1d(y) \le d(x)+1; by the symmetric argument d(x)≤d(y)+1d(x) \le d(y) + 1. Combining, ∣d(x)−d(y)∣≤1|d(x)-d(y)| \le 1. Suppose, for contradiction, that some edge xy∈Exy \in E has both endpoints in the same class, i.e., d(x)d(x) and d(y)d(y) have the same parity. By the key fact, ∣d(x)−d(y)∣≤1|d(x)-d(y)| \le 1, and since they have the same parity, this forces d(x)=d(y)d(x) = d(y); call this common value ℓ\ell. Let PxP_x be a shortest v0v_0–xx path of length ℓ\ell and PyP_y a shortest v0v_0–yy path of length ℓ\ell. Let ww be the last common vertex shared by PxP_x and PyP_y when both are traversed from v0v_0 (such a ww exists since both paths start at v0v_0; possibly w=v0w = v_0 itself). Because PxP_x and PyP_y are shortest paths, the sub-path of PxP_x from v0v_0 to ww and the sub-path of PyP_y from v0v_0 to ww must have the same length, say mm — otherwise one of Px,PyP_x, P_y would not be a shortest path to its endpoint (we could replace its initial segment with the shorter one from the other path and shortcut). Now form the closed walk:

w→⋯→x  (along Px, length ℓ−m)  →  y  (edge xy, length 1)  →⋯→w  (along Py reversed, length ℓ−m).w \to \cdots \to x \;(\text{along } P_x,\text{ length } \ell - m) \;\to\; y \;(\text{edge } xy,\text{ length } 1)\;\to \cdots \to w\;(\text{along } P_y \text{ reversed, length } \ell - m).

This closed walk has total length (ℓ−m)+1+(ℓ−m)=2(ℓ−m)+1(\ell - m) + 1 + (\ell - m) = 2(\ell-m)+1, which is odd. A closed walk of odd length in a graph always contains a cycle of odd length as a subgraph. (This standard fact follows by induction on walk length: if the closed walk is not itself a simple cycle, it repeats some vertex before returning to ww, splitting it into two shorter closed walks whose lengths sum to the original odd length; since the sum of two lengths is odd, at least one of the two shorter closed walks has odd length, and we recurse. The base case is a closed walk with no repeated vertices other than start/end, which is by definition a simple cycle, and it is odd because we never discarded odd length along the recursion.) Hence GG would contain an odd cycle, contradicting our hypothesis that GG has no odd cycle. This contradiction shows no such edge xyxy exists: every edge of GG has endpoints of different parity in d(⋅)d(\cdot), i.e., one endpoint in AA and one in BB. Therefore (A,B)(A,B) is a valid bipartition of GG, so GG is bipartite. Since GG was an arbitrary connected graph with no odd cycle, and general graphs are bipartite iff each component is, the full theorem follows. ■\blacksquare

∎

Worked examples

Example 1: A graph presented without obvious structure. Let GG have vertex set {1,2,3,4,5,6}\{1,2,3,4,5,6\} and edge set

E={12,23,34,45,56,61,14,25}.E = \{12, 23, 34, 45, 56, 61, 14, 25\}.

This is a 6-cycle 1−2−3−4−5−6−11{-}2{-}3{-}4{-}5{-}6{-}1 with two extra "chord" edges 1414 and 2525 added. Is GG bipartite? Attempt via BFS layering. Root at v0=1v_0 = 1. Compute distances via breadth-first search:

  • d(1)=0d(1) = 0.
  • Neighbors of 11: 2,6,42, 6, 4 (from edges 12,61,1412, 61, 14), so d(2)=d(6)=d(4)=1d(2)=d(6)=d(4)=1.
  • Neighbors of 22: 1,3,51,3,5; new vertex is 33, and also 55 via edge 2525, so d(3)=d(5)=2d(3) = d(5) = 2 (both reached in one more step from 22).
  • Neighbors of 66: 5,15,1; 55 already has d(5)=2d(5)=2, consistent.
  • Neighbors of 44: 3,5,13,5,1; 33 and 55 already assigned d=2d=2, consistent.
  • All 6 vertices now have distances: d(1)=0d(1)=0, d(2)=1d(2)=1, d(4)=1d(4)=1, d(6)=1d(6)=1, d(3)=2d(3)=2, d(5)=2d(5)=2.

Set A={1,3,5}A = \{1,3,5\} (even distance) and B={2,4,6}B = \{2,4,6\} (odd distance). Check every edge: 1212: 1∈A,2∈B1\in A, 2\in B ✓. 2323: 2∈B,3∈A2\in B,3\in A ✓. 3434: 3∈A,4∈B3\in A,4\in B ✓. 4545: 4∈B,5∈A4\in B,5\in A ✓. 5656: 5∈A,6∈B5\in A,6\in B ✓. 6161: 6∈B,1∈A6\in B,1\in A ✓. 1414: 1∈A,4∈B1\in A,4\in B ✓. 2525: 2∈B,5∈A2\in B,5\in A ✓. Every edge crosses AA–BB. So GG is bipartite, with bipartition A={1,3,5}A=\{1,3,5\}, B={2,4,6}B=\{2,4,6\} — despite having 8 edges and looking "denser" than a plain cycle. Consistency check via the theorem: does GG have any odd cycle? The outer hexagon has length 6 (even). The chords split it into smaller cycles: 1−2−5−6−11{-}2{-}5{-}6{-}1 has length 4, and 2−3−4−5−22{-}3{-}4{-}5{-}2 has length 4, and 1−4−5−6−11{-}4{-}5{-}6{-}1 has length 4, and 1−2−3−4−11{-}2{-}3{-}4{-}1 has length 4. All induced small cycles are length 4 (even), consistent with bipartiteness, and no odd cycle can be found — matching the BFS conclusion.

Example 2: A graph that fails, with the obstruction pinpointed. Let HH have vertex set {a,b,c,d,e}\{a,b,c,d,e\} and edges

E={ab,bc,cd,de,ea,ac}.E = \{ab, bc, cd, de, ea, ac\}.

This is the 5-cycle a−b−c−d−e−aa{-}b{-}c{-}d{-}e{-}a with one extra chord acac added. Run BFS from v0=av_0 = a:

  • d(a)=0d(a) = 0.
  • Neighbors of aa: b,e,cb, e, c (edges ab,ea,acab, ea, ac), so d(b)=d(e)=d(c)=1d(b) = d(e) = d(c) = 1.
  • Neighbors of cc (distance 1): b,d,ab, d, a. Vertex dd is new: d(d)=2d(d) = 2. But vertex bb is already assigned d(b)=1d(b) = 1 — same distance as cc! And c,bc,b are adjacent (edge bcbc).

We have found an edge, bcbc, joining two vertices at the same BFS distance (d(b)=d(c)=1d(b) = d(c) = 1) from aa. By the proof of the main theorem, this signals an odd closed walk. Concretely, trace it: a→ca \to c (length 1, via chord) →b\to b (length 1, via edge cbcb) →a\to a (length 1, via edge baba) — a closed walk of length 3, in fact exactly the triangle a−c−b−aa{-}c{-}b{-}a, since acac, cbcb, baba are all edges of HH. This triangle is an odd cycle (length 3) sitting inside HH. By the necessity direction of the theorem, HH cannot be bipartite — and indeed, no valid 2-coloring exists: try A={a}A = \{a\}, forcing b,c,e∈Bb,c,e \in B (all adjacent to aa); but then edge bcbc has both endpoints in BB, a contradiction, exactly as the theorem predicts.

CounterexampleWhy connectedness bookkeeping matters — a disconnected trap

The theorem is stated for a general (possibly disconnected) graph GG, and the proof handles disconnection correctly by treating each component separately. But it is instructive to see what goes wrong if one is careless about applying the BFS-layering construction to a disconnected graph as if it were connected. Take GG to be the disjoint union of a triangle T={x,y,z}T = \{x,y,z\} with edges xy,yz,zxxy, yz, zx, and a single edge component {p,q}\{p,q\} with edge pqpq. This graph is not bipartite: the triangle TT is an odd cycle, so by the necessity direction, no bipartition of the whole graph can work, since triangle TT alone already cannot be 2-colored properly. Now suppose a careless reader tries to run BFS from a single vertex v0=xv_0 = x and declare "AA = even-distance vertices, BB = odd-distance vertices" only within reach of v0v_0, then simply tosses pp and qq arbitrarily into AA or BB without checking anything, reasoning "they're in a different component, so it doesn't matter." This reasoning is correct for placement of p,qp,q (indeed, since there is no edge between {x,y,z}\{x,y,z\} and {p,q}\{p,q\}, any assignment of p,qp,q is edge-safe with respect to cross-component edges) — but it is not a proof that the whole graph is bipartite, because BFS from xx never even reaches yy and zz in a way that avoids the internal problem: d(x)=0d(x)=0, and both y,zy,z are neighbors of xx so d(y)=d(z)=1d(y)=d(z)=1, but yy and zz are also adjacent to each other (edge yzyz), so y,zy,z end up in the same class BB, violating the bipartition requirement on edge yzyz. The lesson: the BFS-layering construction, correctly executed, will always self-report a failure (a same-layer edge) whenever an odd cycle exists in the component being explored — it does not silently produce a wrong answer. The trap is only in the reader's temptation to declare success prematurely, without checking every edge within each component, especially when a graph has multiple components and one is misled into thinking "most of the graph works" is the same as "the graph is bipartite." Dropping the discipline of checking every edge, not just cross-component edges, breaks the argument, even though the theorem itself (stated per-component) remains true and needs no extra hypothesis — this counterexample targets sloppy application, not the theorem's logical content.

Scope, edge cases & common traps

SituationWhat happensWhy
GG has no edges at allBipartite (trivially)Vacuously, no edge violates any bipartition; take A=V,B=∅A = V, B = \varnothing
GG is a single vertex, no loopsBipartiteNo edges to violate the condition
GG has a self-loopNot bipartite (by convention)A loop at vv forces vv to be on both sides of the same edge, impossible in a proper 2-coloring; standard treatments exclude loops from simple graphs entirely
GG is disconnectedBipartite iff each component is bipartiteBipartitions of separate components can be chosen independently, since no edges connect them
GG = complete bipartite Km,nK_{m,n}Always bipartiteBy construction, all edges cross the two named parts
GG = odd cycle C2k+1C_{2k+1}Never bipartiteTriangle-style parity argument in the Lemma applies directly
Tree (acyclic connected graph)Always bipartiteNo cycles at all, so vacuously no odd cycle

The mathematician behind it

Origins · 1 minDénes Kőnig and how this was discovered
DK
Dénes Kőnig
1884–1944 · Budapest, Hungary — foundational graph theory and combinatorics

Dénes Kőnig was a Hungarian mathematician who wrote the first systematic textbook on graph theory, Theorie der endlichen und unendlichen Graphen (1936), which crystallized graph theory as an independent mathematical discipline rather than a scattered collection of puzzles. His work connected bipartite structure to matching and covering problems, producing the theorem that bears his name relating maximum matchings to minimum vertex covers in bipartite graphs — a result that presupposes, and deeply illuminates, the bipartite characterization discussed here. Kőnig's insights on bipartite graphs grew out of earlier work by Kőnig's father Gyula Kőnig and contemporaries studying systems of distinct representatives, determinant theory, and combinatorial designs. Kőnig died in Budapest in 1944, during the final months of the Second World War.

History
- 1913: Dénes Kőnig publishes early work formalizing graph-theoretic language for bipartite structures arising from matrix and permutation problems.
- 1916: Kőnig proves what becomes known as König's theorem, relating maximum matchings and minimum vertex covers in bipartite graphs.
- 1931: Kőnig and, independently, Jenő Egerváry, sharpen matching results for bipartite graphs, laying groundwork later used in the Hungarian algorithm for assignment problems.
- 1936: Kőnig publishes the first comprehensive graph theory textbook, cementing bipartite graphs and their odd-cycle characterization as standard material.
- 1950s: The odd-cycle characterization becomes a textbook staple, later generalized in spirit by results on graph coloring, perfect graphs, and hypergraph 2-colorability.
Is the empty graph (no edges) considered bipartite?

Yes. A graph with no edges trivially satisfies the bipartite definition: take A=VA = V and B=∅B = \varnothing (or split VV any way you like), since there are no edges to violate the crossing condition. Vacuous truth applies here exactly as it does in other "for all edges" definitions in graph theory. This edge case matters in inductive proofs and algorithmic base cases, where bipartiteness of graphs with zero edges (or graphs consisting of isolated vertices) is the natural starting point of an induction on the number of edges or vertices.

Does every subgraph of a bipartite graph remain bipartite?

Yes, and this follows immediately from the definition. If GG is bipartite with bipartition (A,B)(A,B), and HH is any subgraph of GG (obtained by deleting some vertices and/or edges), then restrict the same partition to HH's vertex set: every edge of HH is also an edge of GG, so it still crosses between the restricted A∩V(H)A \cap V(H) and B∩V(H)B \cap V(H). This "hereditary" property is why bipartiteness is called a hereditary graph property, and it underlies why the odd-cycle test works: if a subgraph (an odd cycle) is non-bipartite, the whole graph cannot be bipartite either, since the containing graph would have to inherit a valid bipartition down to that odd cycle, which is impossible by the Lemma.

Can a bipartite graph have triangles?

No. A triangle is a cycle of length 3, which is odd, so by the necessity direction of the theorem, any graph containing a triangle as a subgraph cannot be bipartite. This is a quick sanity check: if you ever spot three mutually adjacent vertices in a graph you suspect is bipartite, you can immediately conclude it is not, without running the full BFS test. More generally, bipartite graphs are exactly the triangle-free-of-a-special-kind graphs in the sense that they avoid all odd cycles, not just triangles — a graph can be triangle-free yet still non-bipartite if it contains a longer odd cycle, such as a 5-cycle or 7-cycle.

How is bipartiteness related to 2-colorability and the chromatic number?

They are exactly the same property phrased two ways. A proper 2-coloring assigns colors from {0,1}\{0,1\} to vertices so adjacent vertices differ, which is precisely a bipartition with AA = color-0 vertices and BB = color-1 vertices. Hence "GG is bipartite" and "GG is 2-colorable" are logically identical statements, and the chromatic number χ(G)≤2\chi(G) \leq 2 exactly when GG is bipartite (assuming GG has at least one edge, so χ(G)≥2\chi(G) \geq 2 as well, giving χ(G)=2\chi(G) = 2 precisely for bipartite graphs with an edge). This connects directly to the broader theory of Graph Coloring and Chromatic Number, where bipartite graphs form the simplest nontrivial coloring class.

Is there an efficient algorithm to test bipartiteness, and how fast is it?

Yes — the BFS-layering proof of the sufficiency direction is itself a linear-time algorithm. Run a breadth-first search (or depth-first search) from an arbitrary vertex in each connected component, assigning colors by parity of depth as the traversal proceeds, and check every edge encountered: if an edge ever connects two same-colored vertices, output "not bipartite" (and the specific odd cycle can be reconstructed from the two paths to the least common ancestor in the BFS tree); otherwise output "bipartite" once all components are processed. This runs in O(∣V∣+∣E∣)O(|V| + |E|) time, which is optimal since even reading the input graph takes that long, making bipartiteness testing one of the cleanest examples of an efficiently decidable graph property.

Why does the proof need to consider the "last common vertex" of two shortest paths rather than just concatenating them directly?

Concatenating the two shortest paths PxP_x and PyP_y directly (without trimming to the last common vertex) could produce a closed walk that revisits vertices in a complicated way, making it harder to directly extract a genuine cycle. By trimming to the segment from the last common vertex ww onward, we guarantee the two "tails" of the walk (from ww to xx and from ww to yy) share no other vertices, so concatenating them with the edge xyxy produces a walk that is much closer to a simple cycle, and the general fact that "odd closed walks contain odd cycles" finishes the job regardless of remaining repeated vertices. This bookkeeping keeps the proof airtight rather than relying on an unjustified visual reading of "obviously there's a cycle here."

Does the odd-cycle characterization generalize to directed graphs or hypergraphs?

For directed graphs, bipartiteness is usually still defined on the underlying undirected graph (ignoring edge direction), so the same odd-cycle test applies directly to that undirected version; directions do not change which vertex pairs are adjacent. For hypergraphs, the natural generalization is 2-colorability of hyperedges (avoiding a monochromatic hyperedge), which is a much harder property in general — testing 2-colorability of a hypergraph is NP-complete for hyperedges of size 3 or more, in sharp contrast to the linear-time bipartiteness test for ordinary graphs. This contrast highlights how special the graph case is: the odd-cycle characterization is a genuinely graph-specific phenomenon, not a generic feature of coloring problems.

Before this

Where this leads