Matchings · Bipartite Graphs

Lesson 3

Nikolai Chukhin · Alexander S. Kulikov

At the same time, it is not always the case that a graph is given together with a partition of the set of nodes into two parts. For example, the following \(7 \times 4\) grid graph is bipartite though it may not be immediate from its drawing.

To ensure that it is bipartite, one may specify, for each node, the part it belongs to. To do this, one just assigns labels \(1\) and \(2\) to all nodes and ensures that every edge joins two nodes with different labels. Instead of (or together with) the labels \(1\) and \(2\), one may also use two different colors. Being bipartite is the same as being 2-colorable: we say that a graph is 2-colorable if it is possible to assign one of two colors to every node such that no edge has endpoints of the same color.

from networkx import grid_2d_graph, is_bipartite

print(is_bipartite(grid_2d_graph(7, 4)))

True