Bipartite graphs

A bipartite graph is a graph whose vertices can be split into two groups so that every edge goes from one group to the other. No edge connects two vertices in the same group.

Six scattered vertices drift into two columns of three, one red and one cream. Nine edges then draw in one at a time, each joining a red vertex to a cream vertex, to complete K3,3.
Two sides, nine edges: every edge crosses from one side to the other.

Write the two groups as U and W. Users and films, authors and papers, workers and jobs, students and courses: whenever a network links two different kinds of thing, and never links two things of the same kind, it is bipartite.

The complete bipartite graph K3,3 Three vertices on the left labelled U1 to U3 and three on the right labelled V1 to V3. Every left vertex is joined to every right vertex, nine edges in total, and no two vertices on the same side are joined. U1U2U3V1V2V3
The complete bipartite graph K3,3: three vertices on each side, every left vertex joined to every right vertex, nine edges, none inside a side.

Definition

A graph G = (V, E) is bipartite if its vertex set can be partitioned into two disjoint sets U and W such that every edge has one end in U and the other in W. The sets are called the parts (or partite sets) of the graph.

Two equivalent ways of saying the same thing:

  • Two-colourable. You can colour every vertex black or white so that no edge joins two vertices of the same colour. The colours are the two parts.
  • No odd cycles. A graph is bipartite if and only if it contains no cycle of odd length. (Dénes Kőnig proved this in his 1936 book, the first textbook on graph theory.)

The second version is the one you use in proofs. Walking around a cycle, you alternate sides at every step, so you can only get back to where you started after an even number of steps.

Examples, and non-examples

Graph Bipartite? Why
Any tree (and any forest) Yes Trees have no cycles at all, so no odd ones. Colour by depth, even/odd.
Even cycle C4, C6, … Yes Alternate colours around the cycle.
Odd cycle C3, C5, … No It is an odd cycle.
Hypercube graph Qn Yes Split vertices by whether their bit string has an even or odd number of 1s; every edge flips exactly one bit.
Complete graph Kn, n ≥ 3 No Any three vertices form a triangle.
Petersen graph No Its shortest cycles have length 5. It needs three colours.
Grid graphs, chessboard squares joined to neighbours Yes Colour like a chessboard.
Complete bipartite graph Km,n Yes By construction.

Our hypercube tee is bipartite. Our complete graph tee and the Petersen graph tee are not, and the Petersen graph explainer shows the 5-cycles that rule it out.

Complete bipartite graphs, Km,n

In the complete bipartite graph Km,n, one part has m vertices, the other has n, and every vertex in the first part is joined to every vertex in the second. It has m + n vertices and m·n edges.

Two famous ones:

  • K3,3, the utility graph: three houses, three utilities (water, gas, electricity), can you connect each house to each utility without crossings? No. K3,3 is non-planar, and by Kuratowski's theorem every non-planar graph contains a subdivision of K3,3 or K5.
  • K1,n, the star: one hub joined to n leaves.

A bipartite graph on n vertices has at most ⌊n²/4⌋ edges, reached by the most balanced complete bipartite graph. That is Mantel's theorem from 1907, the first case of Turán's theorem.

How to test whether a graph is bipartite

Run a breadth-first (or depth-first) search and colour as you go: the start vertex is black, its neighbours are white, their unvisited neighbours are black, and so on. If you ever find an edge between two vertices of the same colour, you have found an odd cycle and the graph is not bipartite. Otherwise the colouring gives you the two parts. This takes O(V + E) time, linear in the size of the graph.

In Python with NetworkX:

import networkx as nx
from networkx.algorithms import bipartite

G = nx.complete_bipartite_graph(3, 3)      # K3,3
print(nx.is_bipartite(G))                  # True
left, right = bipartite.sets(G)            # the two parts (G must be connected)
print(sorted(left), sorted(right))         # [0, 1, 2] [3, 4, 5]

print(nx.is_bipartite(nx.petersen_graph()))   # False: it has 5-cycles
print(nx.is_bipartite(nx.hypercube_graph(4))) # True

For a disconnected graph, bipartite.sets needs to be told which nodes go on the top side, because each component can be flipped independently.

Matchings: where bipartite graphs earn their keep

A matching is a set of edges with no shared endpoints: each worker gets at most one job, each job at most one worker. Bipartite graphs are where matching theory is cleanest.

  • Hall's marriage theorem (1935). A bipartite graph with parts U and W has a matching that covers all of U if and only if every subset S of U has at least |S| neighbours in W.
  • Kőnig's theorem (1931). In a bipartite graph, the size of a maximum matching equals the size of a minimum vertex cover. This fails for general graphs (a triangle has maximum matching 1 but needs 2 vertices to cover it).
  • The Hungarian algorithm. Harold Kuhn's 1955 algorithm for the assignment problem (match workers to jobs at minimum total cost) was named after the Hungarian mathematicians Dénes Kőnig and Jenő Egerváry, whose results it builds on.
  • Hopcroft–Karp (1973) finds a maximum matching in a bipartite graph in O(E√V) time. NetworkX: bipartite.maximum_matching(G).

Bipartite graphs in machine learning and data

  • Recommender systems. The user–item interaction graph is bipartite. Matrix factorisation is, in graph terms, learning embeddings for both sides so that observed edges score high.
  • Restricted Boltzmann machines. The "restricted" in RBM means the connection graph between visible and hidden units is bipartite (complete bipartite, in fact): no visible–visible or hidden–hidden weights. That is exactly what makes block Gibbs sampling possible.
  • Factor graphs. Variables on one side, factors on the other. Belief propagation passes messages along this bipartite graph.
  • Hypergraphs and knowledge graphs. Any hypergraph can be stored as a bipartite incidence graph (nodes on one side, hyperedges on the other). The same trick turns n-ary relations into something a property-graph database can hold.
  • Assignment in detection models. DETR-style object detectors match predicted boxes to ground-truth boxes with the Hungarian algorithm before computing the loss.

Adjacency matrix shape

Order the vertices with the U part first. Then the adjacency matrix has a block form

A = [ 0   B ]
    [ Bᵀ  0 ]

where B is the |U| × |W| biadjacency matrix. The zero blocks are the "no edges inside a part" rule. One consequence: the eigenvalues of a bipartite graph's adjacency matrix are symmetric about zero. If λ is an eigenvalue, so is −λ.

FAQ

Is a tree bipartite? Yes. Every tree is bipartite, because a tree has no cycles at all.

Can a bipartite graph have a triangle? No. A triangle is a cycle of length 3, which is odd.

Is the empty graph bipartite? Yes. With no edges, any split of the vertices works.

What is the difference between bipartite and complete bipartite? Bipartite only says edges never stay inside a part. Complete bipartite adds that every possible edge between the parts is present.

Is the Petersen graph bipartite? No. It contains 5-cycles, and its chromatic number is 3. See the Petersen graph explainer.

Is a hypercube bipartite? Yes. Each edge changes exactly one bit, so it always connects an even-weight vertex to an odd-weight one.

Related: the Petersen graph explained, the classic graph that is not bipartite: 10 vertices, 15 edges, and 5-cycles everywhere. Or give every edge a direction: directed acyclic graphs explained covers topological sort, Airflow and git. The hypercube graph explained works the even/odd-parity split out in full.

The graph on a shirt

The hypercube on the Out of the Box tee (Hypercube Graph Tee, €45) is a bipartite graph you can wear: split its vertices by even and odd bit strings and every edge crosses between the two sides. The rest of the line, including the Petersen graph, the complete graph, Erdős–Rényi, scale-free and small-world networks, is in the Graphs collection. Buying for a mathematician? See our gifts for mathematicians guide.

Sources

Back to blog