Bipartite

Bipartite refers to a structure whose vertex set can be divided into two disjoint sets such that every edge connects a vertex from one set to a vertex from the other; equivalently, there are no edges between vertices within the same set. The two sets, or parts, are often called partitions.

A graph is bipartite if and only if it contains no odd cycle, which is equivalent to being 2-colorable: its vertices can be colored using two colors so that adjacent vertices have different colors. If a graph is disconnected, this property must hold for each connected component. In practice, a bipartite graph can be represented, after a suitable relabeling of vertices, with a block off-diagonal adjacency structure.

Common examples include complete bipartite graphs K_{m,n}, where every vertex in one part is connected to every vertex in the other, and even cycles C_{2n}, which are bipartite. All trees are bipartite, since they contain no cycles.

Bipartite graphs are central to bipartite matching problems, which seek maximum matchings that pair vertices from the two parts. Hall’s marriage theorem provides necessary and sufficient conditions for the existence of perfect matchings. Algorithmically, testing bipartiteness is often done by BFS two-coloring; encountering a conflict indicates an odd cycle and thus a non-bipartite graph.

In broader mathematical usage, the term bipartite means partitionable into two distinct parts and is employed in contexts beyond graph theory as well. See also graph theory, bipartite graphs, two-coloring, and Hall’s marriage theorem.