In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint sets U and V (that is, U and V are each independent sets) such that every edge connects a vertex in U to one in V. Vertex sets U and V are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles

```
In [1]:
```import networkx as nx
import matplotlib.pyplot as plt
%matplotlib inline

```
In [2]:
```import queue
def bfs_color(graph, node, color):
q = queue.LifoQueue()
q.put(node)
color[node] = 0
while not q.empty():
node = q.get()
for v in graph[node]:
if color[v] is None:
color[v] = 1 - color[node]
q.put(v)
elif color[v] != 1 - color[node]:
raise ValueError("graph not bipartite")
def bfs(graph):
n = len(graph)
color = [None] * n
for i in range(n):
if color[i] is None:
bfs_color(graph, i, color)
return color

```
In [3]:
```def draw_graph(graph, figsize=(10, 10)):
partition = bfs(graph)
plt.figure(figsize=figsize)
plt.axis('off')
colors = ['steelblue', 'red']
node_color = [colors[partition[i]] for i in graph]
pos = nx.circular_layout(graph)
nx.draw_networkx(graph, node_size=800, pos=pos, node_color=node_color, font_color='white')

```
In [4]:
```graph = nx.Graph()
graph.add_nodes_from(range(6))
graph.add_edges_from([
(0, 1), (1, 2), (1, 4),
(3, 4), (4, 5), (5, 2),
(0, 5), (2, 3), (3, 0)
])
draw_graph(graph)

```
```

```
In [5]:
```graph = nx.complete_multipartite_graph(10, 10)
pos = nx.circular_layout(graph)
draw_graph(graph, figsize=(20, 20))

```
```

```
In [6]:
```graph = nx.complete_multipartite_graph(20, 20)
pos = nx.circular_layout(graph)
draw_graph(graph,figsize=(30, 30))

```
```