A bipartite graph, also called a bigraph, is a set of graph vertices decomposed into two disjoint sets such that no two graph
vertices within the same set are adjacent. The two vertex classes are said to
form a bipartition. A bipartite graph is a special
case of a k-partite graph with 
. The illustration above shows some bipartite graphs, with
vertices in each graph colored based on to which part of the bipartition they belong.
Bipartite graphs are equivalent to two-colorable graphs. All acyclic graphs are bipartite. A cyclic graph is bipartite iff all its cycles are of even length (Skiena 1990, p. 213).
If a bipartite graph has bipartition classes 
and 
, then any Hamiltonian cycle
alternates between 
and 
and so requires 
.
Similarly, any Hamiltonian path alternates between
the classes, and so requires 
. Thus a connected bipartite graph with unequal
bipartition sizes is nonhamiltonian and one
with bipartition sizes differing by more than 1 is untraceable.
These converses do not hold in general: the E graph and
H graph have equal bipartition sizes but are nonhamiltonian
(indeed untraceable), while the fork
graph and spoke graph 
have bipartition sizes differing by 1 but are also untraceable.
Families of bipartite graphs include
1. acyclic graphs (i.e., trees and forests),
2. book graphs 
,
4. crown graphs 
,
5. cycle graphs 
,
6. gear graphs,
7. grid graphs,
8. Haar graphs,
9. Hadamard graphs,
10. hypercube graphs 
,
11. knight graphs,
12. ladder graphs,
13. ladder rung graphs 
(which are forests).
14. path graphs 
(which are trees),
17. stacked book graphs,
18. star graphs 
(which are trees).
König's line coloring theorem states that every bipartite graph is a class 1 graph. The König-Egeváry theorem states that the matching number (i.e., size of a maximum independent edge set) equals the vertex cover number (i.e., size of the smallest minimum vertex cover) are equal for a bipartite graph.
A graph may be tested in the Wolfram Language to see if it is a bipartite graph using BipartiteGraphQ[g], and the indices of one of the components of a bipartite graph can be found using FindIndependentVertexSet[g][[1]].
The numbers of bipartite graphs on 
, 2, ... nodes are 1, 2, 3, 7, 13, 35, 88, 303, ... (OEIS
A033995).
The numbers of connected bipartite graphs on 
, 2 ... nodes are 1, 1, 1, 3, 5, 17,
44, 182, ... (OEIS A005142).
