# Definition(s)

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

# Algorithm(s)

``````

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')

``````

# Run(s)

``````

In [4]:

graph = nx.Graph()
(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))

``````
``````

``````