Download Wolfram Notebook

A bipartite graph, also called a bigraph, is a graph whose vertex set can be 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 ,

3. crossed prism 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),

15. Mongolian tent graphs,

16. Sierpiński carpet graphs,

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-Egervá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 a minimum vertex cover) for a bipartite graph.

A graph may be tested in the Wolfram Language to see if it is a bipartite graph using BipartiteGraphQ[g].

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).

See also

Bicolorable Graph, Bicubic Graph, Bipartite Double Graph, Bipartite Graph Isomorphism, Bipartite Kneser Graph, Bipartition, Complete Bipartite Graph, Graph Two-Coloring, k-Partite Graph, König-Egerváry Theorem, König's Line Coloring Theorem, Tutte Bicubic Graph Conjecture

Explore with Wolfram|Alpha

References

Chartrand, G. Introductory Graph Theory. New York: Dover, p. 116, 1985.Read, R. C. and Wilson, R. J. An Atlas of Graphs. Oxford, England: Oxford University Press, 1998.Saaty, T. L. and Kainen, P. C. The Four-Color Problem: Assaults and Conquest. New York: Dover, p. 12, 1986.Skiena, S. "Coloring Bipartite Graphs." §5.5.2 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 213, 1990.Sloane, N. J. A. Sequences A005142 and A033995 in "The On-Line Encyclopedia of Integer Sequences."Steinbach, P. Field Guide to Simple Graphs. Albuquerque, NM: Design Lab, 1990.

Referenced on Wolfram|Alpha

Bipartite Graph

Cite this as:

Weisstein, Eric W. "Bipartite Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/BipartiteGraph.html

Subject classifications