Lesson 14

Below, we discuss which of the basic graphs are bipartite.

• Path graph.  Any path graph \(P_{n}\) is clearly bipartite.

  



• Cycle graph.  A cycle graph \(C_{n}\) is bipartite if and only if \(n\) is even (we assume that \(n \ge 3\)).

  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
  

  
  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.

  



• Tree.  Any tree is bipartite. Indeed, one can first turn a tree into a rooted tree (by selecting an arbitrary node to be the root) and then color all nodes on odd layers red and color all the remaining nodes blue. See an example below.

  



• Complete graph.  The complete graph \(K_{n}\) is bipartite only when \(n \le 2\). Indeed, when \(n=1\) or \(n=2\), a bipartition is straightforward. For any \(n \ge 3\), \(K_{n}\) contains three different nodes with all three edges between them. This is a cycle on three nodes and already this cycle is not bipartite (as discussed above).
  At the same time, there exists yet another important class of graphs that are bipartite just by definition: \(K_{n,m}\) is the complete bipartite graph with parts of size \(n\) and \(m\).
  

  

  
  

  from networkx import complete_bipartite_graph, nx_agraph
  
  k47 = complete_bipartite_graph(4, 7)
  nx_agraph.to_agraph(k47).draw('k47.png', prog='dot')