Bipartite graph

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.

A bipartition of a graph divides its vertex set into two independent sets, so every edge joins different parts. A graph admitting such a partition of a set is a bipartite graph. The two parts are not generally unique: separate connected components of a graph can have their sides exchanged independently, and isolated vertices can be assigned to either part.

A lattice interaction graph is bipartite if its sites split into two sets such that every interaction bond joins opposite sets. An even nearest-neighbour ring has this property. It permits a two-sublattice Néel state and a bipartite spin rotation; an odd antiferromagnetic ring is frustrated.

A crown graph is a complete bipartite graph with a perfect matching removed. For $n\ge 2$ it has chromatic number two, but greedy coloring in the order $a_1,b_1,a_2,b_2,\dots ,a_n,b_n$ uses $n$ colors: the matched pair gets the same new color, and every subsequent pair sees all earlier colors.

For a bipartite graph with ordered parts $X,Y$, its biadjacency matrix has rows indexed by $X$ and columns indexed by $Y$, with entry one for an edge and zero otherwise. It has size $|X|$ by $|Y|$, rather than the square full bipartite adjacency matrix on $X\bigsqcup Y$, which is the block matrix $\left(\begin{array}{cc}0& M\\ M^{\mathsf{T}}& 0\end{array}\right)$. Its singular values describe the normalized adjacency operator of a bipartite graph after division by $\sqrt{|X||Y|}$.

Equip the function spaces of the two nonempty parts of a bipartite graph with uniform inner products. Its normalized adjacency operator is $({\theta }_{G}v)(x)={\mathbb{E}}_{y}G(x,y)v(y)$. In orthonormal coordinate bases, its matrix is $G/\sqrt{|X||Y|}$, not the unscaled adjacency matrix. For a biregular graph of edge density of a bipartite graph $\gamma$, constant functions give a largest singular value $\gamma$, and the remaining singular values belong to the centered kernel $G-\gamma$.

A biregular graph is a bipartite graph whose vertices have constant degree on each part separately. The two degree constants can differ. If its parts are $X,Y$ and its edge density of a bipartite graph is $\gamma$, the two degrees are $\gamma |Y|$ and $\gamma |X|$. Thus its adjacency function has constant row and column averages $\gamma$.

For a biregular graph with $m$ left vertices of degree $r$ and $n$ right vertices of degree $s$, let $X$ be the indicator vector of a uniformly selected independent set. Use base-two information entropy. Shearer inequality gives $H(X_U)\le r^{-1}{\sum }_{w\in W}H(X_{N(w)})$. Conditional on $X_U$, each right vertex with an empty selected neighbourhood is an independent fair binary choice, and the other right vertices are forbidden. Writing $q_w=\mathbb{P}(X_{N(w)}=0)$ gives $H(X)\le r^{-1}{\sum }_w[H(X_{N(w)})+r{q}_w]$. For the $2^s$ neighbourhood patterns, assign weight $2^r$ to the zero pattern and weight one to all others. Jensen's inequality implies $H(Y)+r{q}_w\le {\log }_2(2^r+2^s-1)$. Since $n/r=m/s$, the bound follows from $H(X)={\log }_{2}i(G)$. If $s$ divides $m$, the disjoint union of $m/s$ copies of the complete bipartite graph $K_{s,r}$ attains equality: each component has $2^s+2^r-1$ independent sets.

For a biregular graph of edge density of a bipartite graph $\gamma$, small rectangular discrepancy, a box norm fourth power close to ${\gamma }^4$, and a small second singular value of the normalized adjacency operator of a bipartite graph are equivalent notions of quasirandomness, with quantitative bounds independent of the part sizes. Centering the adjacency function removes the constant singular component.

Let $H=M-\delta J$ be the centered biadjacency matrix of an equal-part biregular graph, and put $s=\Vert H{\Vert }_{\mathrm{op}}$. For subsets $A,B$ of the two parts, their edge discrepancy is $1_A^{\mathsf{T}}H{1}_B$. The Cauchy-Schwarz inequality proves the displayed bound. If the part size is $n$, centering the two indicator vectors improves it to $sn\sqrt{\alpha (1-\alpha )\beta (1-\beta )}$. The centered four-cycle identity for a biregular graph shows that $t_4(G)\le {\delta }^4(1+c^4)$ implies $s\le c\delta n$ for $c\ge 0$.

For an equal-part biregular graph with part size $n$ and degree $\delta n$, let $M$ be its biadjacency matrix and $H=M-\delta J$, where $J$ is the all-ones matrix. The constant row and column sums make $H$ annihilate constants on both sides. Since $M{M}^{\mathsf{T}}={\delta }^{2}nJ+H{H}^{\mathsf{T}}$ and the two summands have zero products, their squared matrix trace splits as displayed. The bipartite four-cycle density counts the squared matrix trace of $M{M}^{\mathsf{T}}$ divided by $n^4$.

A half graph has two vertex classes $X=\{x_1,\dots ,x_n\}$ and $Y=\{y_1,\dots ,y_n\}$, with $x_i$ adjacent to $y_j$ exactly when $i\le j$. Its nested vertex neighbourhoods give a useful obstruction to partitions in which every pair is a regular pair of vertex sets.

Partition both sides of a half graph into classes of size at least $100$. A class of size $s$ has at most $2\lceil s/10\rceil$ elements with fewer than $s/10$ class elements on one side in the underlying order. If there are $k_X$ and $k_Y$ classes, the union of these boundary elements has size at most $2n/5+2(k_X+k_Y)\le 11n/25$. Some index $m$ is therefore away from both boundaries. The class containing $m$ on each side has at least one tenth of its points strictly above $m$ and strictly below $m$. Choosing lower $X$ points with upper $Y$ points, or upper $X$ points with lower $Y$ points, yields edge density of a bipartite graph values one and zero. Both cannot be within $1/10$ of the same class-pair edge density of a bipartite graph, so that pair is not a $1/10$-regular pair of vertex sets.

A graph is bipartite if and only if it contains no odd cycle. One direction follows because every cycle alternates between the two vertex classes. For the converse, in each connected component of a graph choose a root and partition the vertices according to the parity of their graph distance from it. An edge joining equal parities would close an odd cycle, so every edge crosses the partition.

The complete bipartite graph $K_{r,s}$ has vertex classes of sizes $r$ and $s$ and contains all $rs$ edges between the classes.

If a bipartite graph with class sizes $m,N$ has at least $\beta mN$ edges, double count pairs consisting of an $s$-set in the first class and a common neighbour in the second. Convexity of binomial coefficients gives some $S$ with $|N(S)|\ge N\left(\genfrac{}{}{0ex}{}{\lfloor \beta m\rfloor }{s}\right)/\left(\genfrac{}{}{0ex}{}{m}{s}\right)$. When $s\le \beta m/2$, the quotient is at least $(\beta /2{)}^s$. This turns density into a large complete bipartite subgraph.

A star graph is the complete bipartite graph with one centre and $m$ leaves. Any pair of its edges meet at the centre.

A finite graph is bipartite exactly when it has a proper colouring with two colours. Equivalently,for its chromatic polynomial.