What Is a Bipartite Graph?

A bipartite graph is a graph whose vertex set can be divided into two disjoint subsets such that every edge connects a vertex in one subset to a vertex in the other, with no edges existing between vertices within the same subset. This two-part structure makes bipartite graphs a fundamental object in combinatorics, network analysis, and theoretical computer science. A well-known characterization, König's theorem, establishes that a graph is bipartite if and only if it contains no odd-length cycles.

Bipartite graphs arise naturally wherever relationships exist between two distinct classes of objects: users and resources, jobs and workers, or documents and terms. The structure's two-partition property gives it clean algebraic characteristics, including an adjacency matrix whose eigenvalue spectrum is antisymmetric around zero. These properties make bipartite graphs both theoretically tractable and practically versatile, as described in overviews published through the ACM Digital Library on graph-theoretic methods in network analysis.

Structure and Properties

The formal definition of a bipartite graph G = (U, V, E) requires every edge in E to have one endpoint in U and the other in V. A complete bipartite graph, denoted K(m,n), connects every vertex in U to every vertex in V, yielding m times n edges. Bipartite graphs admit a two-coloring of vertices such that no two adjacent vertices share the same color, and this two-colorability is equivalent to the absence of odd cycles. Spectral analysis of bipartite graphs reveals that the nonzero eigenvalues of the adjacency matrix appear in positive-negative pairs, a property that simplifies algorithms for clustering and partitioning. The ScienceDirect overview of bipartite graphs documents this spectral characterization and its use in machine learning applications such as soft clustering and dimensionality reduction.

Matching Theory

Matching in bipartite graphs is among the most studied problems in combinatorial optimization. A matching is a subset of edges in which no two edges share a vertex; a maximum matching is the largest such subset. The Hungarian algorithm, also known as the Kuhn-Munkres method, solves the assignment problem by finding maximum-weight matchings in polynomial time. Hall's Marriage Theorem provides a necessary and sufficient condition for a perfect matching to exist: every subset S of U must have at least |S| neighbors in V. These results underpin scheduling systems, resource allocation, and task assignment in distributed computing environments.

Graph Algorithms and Representations

Bipartite graphs are commonly represented using adjacency matrices or adjacency lists, and the two-partition structure enables efficient algorithmic solutions. Breadth-first search is the standard method for testing bipartiteness, running in O(V + E) time. Random bipartite graphs are used as building blocks in low-density parity-check (LDPC) codes, where the Tanner graph representation connects variable nodes to check nodes through a bipartite structure. This application, widely studied in coding theory, connects bipartite graphs to information theory and error-correcting code design, an active area in IEEE Xplore publications on channel coding.

Applications

Bipartite graphs have applications in a wide range of fields, including:

• Network flow and resource allocation, where edges model supply-demand relationships
• Recommendation systems, modeling user-item interactions in collaborative filtering
• Error-correcting codes, through Tanner graphs used in LDPC decoding
• Bioinformatics, representing protein-protein interaction networks between two functional classes
• Database query optimization, where join operations map to bipartite matching problems