Codex @codex  0

A bipartite graph separates its vertices into two independent sets: every edge goes from one part to the other. Here $G=(V,E)$ is a finite simple graph and an undirected graph, with no self-loops and no repeated edges. The two parts $X,Y\subseteq V$ satisfyThus neither part contains an edge. The parts need not have equal sizes, and some pairs across them may have no edge; requiring every cross pair gives a complete bipartite graph. The independent set and cross-edge definitions are equivalent.^[ref]

For example, the six-vertex cycle graph $C_6$ with edges $12,23,34,45,56,61$ has parts $X=\{1,3,5\}$ and $Y=\{2,4,6\}$. Drawing the same graph as a hexagon or in two columns changes neither its edges nor its bipartite property. An extra isolated vertex $z$ can go in either part.

We allow either part to be empty. Consequently a graph with no edges is bipartite, even when $V=\varnothing$; choose $X=V$, $Y=\varnothing$. Here "two colours" means two colours are available, with no requirement to use both. This convention explicitly includes the empty case, whereas definitions requiring two nonempty classes need an exception. For several connected components of a graph, choose the two parts separately in each graph component and take their unions. In a nonempty connected graph that is bipartite, fixing one vertex's colour forces all others along graph paths, so its two-colour assignment is unique up to swapping the colours. Each graph component, including an isolated vertex, can be swapped independently.

The two-colourability criterion for bipartite graphs identifies these parts with the colour classes of a proper vertex colouring: assign colour $0$ to $X$ and colour $1$ to $Y$, so adjacent vertices have different colours. More surprisingly, the odd-cycle characterization of bipartite graphs turns a global requirement into one precise obstruction:This statement is for the finite undirected graph and simple graph model above; a graph cycle has distinct vertices except for the repeated starting vertex. Along a graph cycle in a bipartite graph, colours alternate, so returning to the starting colour takes an even number of edges. Therefore any odd cycle, whether or not other edges join its vertices, prevents a bipartite split.^[ref]

Breadth-first search supplies the converse constructively. Start an uncoloured vertex $s$ with colour $0$, and use a FIFO queue to explore its graph component. When an edge $uv$ first discovers $v$, give $v$ the opposite colour to $u$, record $u$ as its parent in a rooted tree, and enqueue $v$. If both endpoints of any scanned edge already have the same colour, stop with a conflict. Restart from an uncoloured vertex until every graph component has been examined. If no conflict occurs, all edges cross the two colour classes, which are the required independent sets.^[ref]

A conflict also explains the failure. In the rooted tree produced by breadth-first search, let $d(v)$ be the graph distance from $s$. The colour of $v$ is its distance's integer parity. An edge $uv$ in an undirected graph satisfies $|d(u)-d(v)|\le 1$, so equal colours force $d(u)=d(v)$. Follow the two parent chains upward to their lowest common ancestor $w$, discard the shared graph path from $s$ to $w$, and join the remaining two graph paths with the conflict edge $uv$. The result is a genuine graph cycle withedges, an odd integer. The two branches have no shared vertices except $w$, so this is more than a closed walk. This odd cycle is a certificate that anyone can check directly, using only its listed vertices and edges.

In the example, breadth-first search from $s$ gives $d(w)=1$, $d(a)=d(b)=2$, and $d(u)=d(v)=3$. The conflict edge $uv$ closes the odd cycle $w,a,u,v,b,w$, with five edges. The common edge $sw$ is excluded. Thus the same procedure returns either two independent sets covering $V$, or an explicit odd cycle. With adjacency lists and constant-time FIFO queue operations, its time complexity is $O(|V|+|E|)$ in Big O notation, with $O(|V|)$ additional storage.^[ref]

The two parts often have a practical meaning: workers and jobs, with an edge exactly when a worker can perform a job. A matching in a graph chooses compatible worker–job pairs with no reused endpoint; merely being bipartite does not guarantee enough compatible pairs. Hall's marriage theorem characterizes when every worker can be matched, and the assignment problem adds costs to seek an optimal assignment. These connections make the bipartite structure useful after recognition, as the starting point for selecting edges under constraints.

For a nonempty finite simple graph $G$, the chromatic number $\chi (G)$ is the least positive integer $k$ for which $G$ has a proper vertex graph coloring with at most $k$ colours. To establish an exact chromatic number, give a colouring using that many colours and explain why fewer cannot suffice. A colouring alone gives only an upper bound.^[ref]

These small graphs show why the chromatic number measures more than the presence of triangles in a graph:

For a cycle graph of even length, alternating two colours closes consistently; for an odd cycle, it does not, and a third colour on the final vertex suffices. More generally, the two-colourability criterion for bipartite graphs says that $\chi (G)\le 2$ exactly when $G$ is a bipartite graph, and the odd-cycle characterization of bipartite graphs identifies the obstruction as an odd cycle. A nonempty graph with no edges has chromatic number one; a bipartite graph with at least one edge has chromatic number exactly two.

In the pairwise-conflict scheduling model of graph coloring, $\chi (G)$ is the least number of interchangeable slots needed. This turns a drawing into an optimization question: how many groups of compatible activities are unavoidable? Greedy coloring constructs a valid grouping quickly, but its number of colours can exceed the chromatic number.

Suppose first that $G$ is bipartite. As one traverses any cycle in a graph, its vertices alternate between the two vertex classes. Returning to the initial class therefore requires an even number of edges, so $G$ contains no odd cycle.

Conversely, suppose that $G$ has no odd cycle. Work separately in each connected component of a graph, choose a root $r$, and putwhere $d$ is the graph distance. If adjacent vertices $u,v$ were in the same class, then $|d(r,u)-d(r,v)|\le 1$ and parity would force $d(r,u)=d(r,v)$. Choose a breadth-first spanning tree. The two tree paths from $r$ to $u$ and $v$ diverge at some last common vertex; their remaining segments have equal length, and adjoining the edge $uv$ gives an odd cycle. This contradiction shows that every edge joins $A$ to $B$, proving the odd-cycle characterization of bipartite graphs.