bipartit

Bipartit, or bipartite graph, is a concept in graph theory. A graph is bipartit if its vertex set can be partitioned into two disjoint subsets, U and V, such that every edge connects a vertex in U to a vertex in V. There are no edges between vertices within the same subset, and the two subsets form a bipartition of the vertices.

Equivalently, a bipartit graph is 2-colorable: its vertices can be colored with two colors so that no adjacent vertices share a color. Another important characterization is that a graph is bipartit if and only if it contains no odd-length cycle. This makes the property particularly useful for recognizing bipartit graphs: the absence of odd cycles guarantees a valid two-set partition.

Common examples include path graphs, even cycles, and complete bipartite graphs such as K_{m,n}, where every vertex in one part is connected to every vertex in the other. For a connected bipartit graph, the two parts are unique up to swapping the labels of U and V.

Applications and algorithms related to bipartit graphs are widespread in computer science and operations research. They underpin matching problems, such as finding maximum matchings, which are central to resource allocation and scheduling. Algorithms like the Hopcroft–Karp method efficiently compute maximum matchings in bipartite graphs. Practical tests for bipartitness often use breadth-first search to attempt a two-coloring; encountering a conflict indicates the graph is not bipartit.