Bipartite graph

A bipartite graph is a graph whose vertices can be divided into two disjoint sets — traditionally called the "left" and "right" partitions — such that every edge connects a vertex in one set to a vertex in the other. No edge connects vertices within the same partition. This structural constraint makes bipartite graphs the natural representation of matching problems, affiliation networks, and any system in which relationships occur exclusively between distinct categories.

Bipartite graphs appear wherever a system organizes interactions across a categorical boundary. In ecology, they model pollination networks where edges connect pollinators to plants. In economics, they model buyer-seller markets. In recommendation systems, they connect users to items. In academia, they connect authors to papers. The adjacency matrix of a bipartite graph is rectangular rather than square, and its singular values encode the strength of community structure across the partition.

The computational significance of bipartite graphs lies in the efficiency of algorithms that exploit their partition structure. Maximum matching in general graphs is computationally demanding, but in bipartite graphs it reduces to maximum flow, solvable in polynomial time. This is not a coincidence: the bipartite constraint collapses the combinatorial complexity of general matching by eliminating odd-length cycles.

The bipartite graph is often treated as a special case — a restricted class of graph with specialized algorithms. This framing misses its deeper significance. Most real-world relationships are not between arbitrary entities but between entities of different types. The bipartite graph is not a special case of the general graph; it is the general case of a world organized by category. The general graph — where any node can connect to any other — is the abstraction that requires justification, not the bipartite one.