Bipartite graphs

Definition of a Bipartite Graph

A $\text{bipartite graph}$ $G$ is one whose $\text{vertex set}$ can be partitioned into two subsets $A$ and $B$ so that every $\text{edge}$ joins a vertex in $A$ to a vertex in $B$.

Equivalently, the induced subgraphs $G[A]$ and $G[B]$ contain no $\text{edges}$, making them empty graphs on their respective vertex sets.

This structure prohibits any $\text{odd cycle}$ from existing, since an odd cycle would force an edge within one part when you alternate back to the start.

$\mathbf{\text{Example}}$
The graph with $A=\{1,2\}$, $B=\{a,b,c\}$ and edges $\{1a,1b,2b,2c\}$ is bipartite because every edge connects $A$ to $B$.

$\mathbf{\text{Metaphor}}$
Think of two islands $A$ and $B$ connected only by bridges; no bridge ever connects points on the same island.

Characterization by Odd Cycles

A fundamental $\text{theorem}$ states that a graph is $\text{bipartite}$ if and only if it contains no $\text{odd cycles}$.

If an odd cycle existed, alternating vertices would land two consecutive vertices in the same part, contradicting the bipartition.

Conversely, if no odd cycle is present, one can color vertices by distance parity from an arbitrary root, yielding a valid bipartition.

This criterion provides both a theoretical test and a practical BFS coloring algorithm for detecting bipartiteness.

$\mathbf{\text{Example}}$
The cycle $C_4$ is bipartite (no odd cycle), while $C_3$ fails the test due to its length $3$.

$\mathbf{\text{Metaphor}}$
It’s like checking whether you can two-color every step of a dance floor without stumbling back onto your own color in an odd number of moves.

Complete Bipartite Graphs $K_{a,b}$

A $\text{complete bipartite graph}$ $K_{a,b}$ has parts $A,B$ with $|A|=a$, $|B|=b$, and contains every possible $\text{edge}$ between $A$ and $B$.

Such a graph maximizes connectivity across parts while maintaining zero connectivity within each part, yielding $ab$ edges.

Complete bipartite graphs serve as extremal examples and appear in matching theory and network design.

$\mathbf{\text{Example}}$
$K_{2,3}$ connects every one of the 2 vertices in $A$ to all 3 in $B$, totaling $6$ edges.

$\mathbf{\text{Metaphor}}$
Imagine a job fair where every of the $a$ recruiters meets every of the $b$ candidates, and no two recruiters or candidates meet amongst themselves.

Isomorphism of $K_{a,b}$ and $K_{c,d}$

Two complete bipartite graphs $K_{a,b}$ and $K_{c,d}$ are isomorphic exactly when their part sizes match as sets, i.e., $\{a,b\}=\{c,d\}$.

This means either $a=c$ and $b=d$, or $a=d$ and $b=c$, capturing the symmetry of swapping the two parts.

No other relabeling can equate them, since the degree multiset $\{b,b,\dots ,a,a\}$ uniquely identifies the part sizes.

$\mathbf{\text{Example}}$
$K_{2,5}\cong K_{5,2}$ but neither is isomorphic to $K_{3,4}$.

$\mathbf{\text{Metaphor}}$
It’s like two rectangular grids: a $2\times 5$ grid can be turned into a $5\times 2$ grid by rotation, but not into a $3\times 4$ one.

Induced Subgraphs Remain Bipartite

Any induced subgraph of a $\text{bipartite graph}$ inherits the original partition restricted to the selected vertices.

Since no $\text{edges}$ within a part existed originally, none can appear in the induced subgraph.

Thus bipartiteness is preserved under vertex deletion.

$\mathbf{\text{Example}}$
Removing one vertex from $K_{3,3}$ yields a bipartite subgraph with parts sizes $(3,2)$.

$\mathbf{\text{Metaphor}}$
It’s like removing some bridges between two islands—you still have two islands with no internal bridges.

Complete Bipartite Graphs Which Are Trees

A tree is an acyclic connected graph. For $K_{a,b}$ to be a tree, it must have $ab$ edges and no cycles.

Since a tree on $n=a+b$ vertices has exactly $n-1$ edges, we require $ab=a+b-1$.

Solving yields $(a-1)(b-1)=1$, so $\{a-1,b-1\}=\{1,1\}$ giving $a=b=2$.

Hence only $K_{1,1}$ (a single edge) and $K_{2,1}$ (a path of length 2) are complete bipartite trees.

$\mathbf{\text{Example}}$
$K_{1,1}$ is just an edge, $K_{2,1}$ is a 3-vertex path, both trees.

$\mathbf{\text{Metaphor}}$
Imagine two stations connected by all possible rails: only trivial rail lines avoid forming loops.

Regular Bipartite Graphs Have Equal Part Sizes

Let $G$ be a $k$-regular $\text{bipartite graph}$ with parts $A$ and $B$. Each vertex in $A$ has $k$ neighbors in $B$, contributing $k|A|$ cross-edges.

Similarly, vertices in $B$ contribute $k|B|$ cross-edges. Counting the same edges twice gives $k|A|=k|B|$.

Since $k>0$, we conclude $|A|=|B|$.

$\mathbf{\text{Example}}$
A $3$-regular bipartite graph must have the same number of vertices on each side, e.g. $A$ and $B$ both of size 4.

$\mathbf{\text{Metaphor}}$
If every dancer on one side has exactly $k$ partners on the other, both sides must have equal headcounts to match the partnerships.

Conclusion

Bipartite graphs split vertices into two independent parts with no internal edges and avoid $\text{odd cycles}$, ensuring two-colorability.

Complete bipartite graphs $K_{a,b}$ maximize cross-part connections, are isomorphic precisely when $\{a,b\}$ match, and reduce to simple trees only in trivial small cases.

Induced subgraphs of bipartite graphs remain bipartite, and regular bipartite graphs enforce equal part sizes, demonstrating the rich interplay of combinatorial counting and structural constraints in this class of graphs.