Lesson 4

It is not difficult to see that the cycle graph \(C_{n}\) is bipartite if and only if \(n\) is even. Indeed, if \(n\) is even it is easy to \(2\)-color the nodes of \(C_{n}\): say, node \(i\) is red if \(i\) is even and is blue otherwise. Then, every edge of the form \(\{i, i+1\}\) has endpoints of different colors. The “last” edge \(\{1, n\}\) is also colored properly since \(n\) is even.

However, when \(n\) is odd, there is no \(2\)-coloring. To see why, assume that the node \(1\) is red. Then, \(2\) must be blue. Then, \(3\) must be red. Continuing in the same manner, we conclude that odd nodes are red whereas even nodes are blue. But then, the edge \(\{1, n\}\) is monochromatic: both its nodes are red.

from networkx import cycle_graph, is_bipartite

for n in range(4, 8):
    print(n, is_bipartite(cycle_graph(n=n)))

4 True
5 False
6 True
7 False