Graph Theory37 sections · 1633 units
Open in Course

Vocabulary - 2-Coloring

The visual test

Here is another way to think about bipartite graphs: can you color every node with one of two colors (say, red and blue) so that no edge connects two nodes of the same color?

If yes, the graph is bipartite. The red nodes form one group, blue nodes form the other. This is why bipartite graphs are also called "22-colorable." The two concepts are equivalent: if you can split nodes into two groups with edges only between groups, you can 22-color the graph. And if you can 22-color it, you have found the two groups.