= Bipartite graph
{wiki}
= Bipartite
{synonym}
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$ satisfy
$$
X\cap Y=\varnothing,\qquad X\cup Y=V,\qquad \{u,v\}\in E\Longrightarrow (u\in X,\ v\in Y)\ \text{or}\ (u\in Y,\ v\in X).
$$
Thus 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.<Graph Theory by Reinhard Diestel/The Basics (author-hosted chapter preview)>[Section 1.1, printed p. 3, independent vertices; Section 1.6, printed p. 17, bipartite and complete multipartite graphs]{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.
\Image[/bipartite-graph-independent-parts.png]
{title=The same six-cycle and isolated vertex drawn as a cycle and as two independent parts}
{id=bipartite-graph-independent-parts}
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:
$$
G\text{ is bipartite}\quad\Longleftrightarrow\quad G\text{ contains no odd cycle}.
$$
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.<Graph Theory by Reinhard Diestel/The Basics (author-hosted chapter preview)>[Section 1.6, Proposition 1.6.1 and proof, printed pp. 17–18]{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>.<Algorithms, 4th edition by Robert Sedgewick and others/BipartiteX.java>{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)|\leq1$, 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> with
$$
\bigl(d(u)-d(w)\bigr)+\bigl(d(v)-d(w)\bigr)+1=2\bigl(d(u)-d(w)\bigr)+1
$$
<edges>, 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>.
\Image[/bipartite-graph-odd-cycle-certificate.png]
{title=A BFS colour conflict closes a five-cycle; the shared root path is excluded from the certificate}
{id=bipartite-graph-odd-cycle-certificate}
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.<Algorithms, 4th edition by Robert Sedgewick and others/BipartiteX.java>{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.
Back to article page
