Bipartite Graph Check in DSA Python

Mental Model

A bipartite graph can be split into two groups where no nodes inside the same group connect to each other.

Analogy: Imagine two teams playing a game where players only pass the ball to the other team, never to their own teammates.

Group A: 1 -> 3 -> 5
Group B: 2 -> 4 -> 6
Edges only go between groups, never inside one group.

Dry Run Walkthrough

Input: Graph with edges: 1-2, 2-3, 3-4, 4-1 (square cycle)

Goal: Check if the graph can be colored using two colors so that no connected nodes share the same color.

Step 1: Start coloring node 1 with color 0

1[0] -> 2[ ] -> 3[ ] -> 4[ ]

Why: We pick a starting node and assign the first color.

Step 2: Color node 2 with color 1 (opposite of node 1)

1[0] -> 2[1] -> 3[ ] -> 4[ ]

Why: Neighbors must have opposite colors to avoid same-group edges.

Step 3: Color node 3 with color 0 (opposite of node 2)

1[0] -> 2[1] -> 3[0] -> 4[ ]

Why: Continue assigning opposite colors to neighbors.

Step 4: Color node 4 with color 1 (opposite of node 3)

1[0] -> 2[1] -> 3[0] -> 4[1]

Why: Complete coloring all nodes connected in the graph.

Step 5: Check edges for conflicts; none found

1[0] -> 2[1] -> 3[0] -> 4[1]

Why: No two connected nodes share the same color, so graph is bipartite.

Result:

1[0] -> 2[1] -> 3[0] -> 4[1]
Graph is bipartite: True

Annotated Code

DSA Python

from collections import deque

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.adj = [[] for _ in range(vertices)]

    def add_edge(self, u, v):
        self.adj[u].append(v)
        self.adj[v].append(u)

    def is_bipartite(self):
        color = [-1] * self.V
        for start in range(self.V):
            if color[start] == -1:
                queue = deque([start])
                color[start] = 0  # assign first color
                while queue:
                    u = queue.popleft()
                    for v in self.adj[u]:
                        if color[v] == -1:
                            color[v] = 1 - color[u]  # assign opposite color
                            queue.append(v)
                        elif color[v] == color[u]:
                            return False
        return True

# Driver code
# Graph with edges: 1-2, 2-3, 3-4, 4-1 (0-based indexing: 0-1,1-2,2-3,3-0)
g = Graph(4)
g.add_edge(0, 1)
g.add_edge(1, 2)
g.add_edge(2, 3)
g.add_edge(3, 0)

result = g.is_bipartite()
print(f"Graph is bipartite: {result}")

color = [-1] * self.V

Initialize all nodes as uncolored.

for start in range(self.V):

Check each node to cover disconnected graphs.

if color[start] == -1:

Start BFS from uncolored node.

color[start] = 0 # assign first color

Assign first color to start node.

u = queue.popleft()

Process current node in BFS.

for v in self.adj[u]:

Check all neighbors of current node.

if color[v] == -1:

If neighbor uncolored, assign opposite color.

elif color[v] == color[u]:

If neighbor has same color, graph is not bipartite.

Output

Graph is bipartite: True

Complexity Analysis

Time: O(V + E) because we visit each vertex and edge once during BFS

Space: O(V) for the color array and BFS queue

vs Alternative: Naive approach tries all colorings which is exponential; BFS coloring is efficient and linear.

Edge Cases

Empty graph (no vertices)

Returns True since no edges exist to violate bipartite property

DSA Python

for start in range(self.V):

Graph with one vertex and no edges

Returns True as single node can be colored any color

DSA Python

if color[start] == -1:

Graph with odd cycle (e.g., triangle)

Returns False because odd cycles cannot be bipartite

DSA Python

elif color[v] == color[u]:

When to Use This Pattern

When you need to split nodes into two groups with no internal edges, use bipartite check with BFS coloring to verify feasibility.

Common Mistakes

Mistake: Not checking all disconnected components of the graph
Fix: Use a loop over all nodes and start BFS only on uncolored nodes.

Mistake: Assigning the same color to neighbors instead of opposite
Fix: Assign color[v] = 1 - color[u] to ensure opposite colors.

Summary

Checks if a graph can be divided into two groups with no edges inside the same group.

Use when you want to know if a graph is bipartite or can be 2-colored.

The key insight is to color neighbors with opposite colors and detect conflicts.

Practice

1. What does it mean if a graph is bipartite?

easy

A. It has an equal number of vertices and edges

B. Its vertices can be divided into two groups with no edges inside the same group

C. It contains at least one cycle

D. All vertices have the same degree

Solution

1. Step 1: Understand bipartite graph definition

   A bipartite graph means its vertices can be split into two sets where no edge connects vertices within the same set.

2. Step 2: Compare options with definition

   Only Its vertices can be divided into two groups with no edges inside the same group matches this definition exactly. Other options describe different graph properties.

3. Final Answer:

   Its vertices can be divided into two groups with no edges inside the same group -> Option B

4. Quick Check:

   Bipartite = Two groups, no internal edges [OK]

Hint: Bipartite means two groups with edges only between groups [OK]

Common Mistakes:

• Confusing bipartite with equal vertices and edges
• Thinking bipartite means no cycles
• Assuming all vertices have same degree

2. Which of the following Python code snippets correctly initializes a graph as an adjacency list for bipartite check?

easy

A. graph = {0: 1, 1: 2, 2: 3, 3: 0}

B. graph = [[0, 1], [1, 2], [2, 3], [3, 0]]

C. graph = {0: [1, 3], 1: [0, 2], 2: [1, 3], 3: [0, 2]}

D. graph = [0, 1, 2, 3]

Solution

1. Step 1: Identify adjacency list format

   An adjacency list uses a dictionary mapping each vertex to a list of connected vertices.

2. Step 2: Check each option

   graph = {0: [1, 3], 1: [0, 2], 2: [1, 3], 3: [0, 2]} uses a dictionary with lists, correctly representing adjacency. graph = [[0, 1], [1, 2], [2, 3], [3, 0]] is a list of edges, not adjacency list. graph = {0: 1, 1: 2, 2: 3, 3: 0} maps to single vertex, not list. graph = [0, 1, 2, 3] is just a list of vertices.

3. Final Answer:

   graph = {0: [1, 3], 1: [0, 2], 2: [1, 3], 3: [0, 2]} -> Option C

4. Quick Check:

   Adjacency list = dict with lists [OK]

Hint: Adjacency list uses dict with vertex keys and list of neighbors [OK]

Common Mistakes:

• Using list of edges instead of adjacency list
• Mapping vertex to single vertex instead of list
• Using just a list of vertices without edges

3. What is the output of this Python code that checks if the graph is bipartite?

def is_bipartite(graph):
    color = {}
    def dfs(node, c):
        if node in color:
            return color[node] == c
        color[node] = c
        return all(dfs(nei, 1 - c) for nei in graph[node])
    return all(dfs(node, 0) for node in graph if node not in color)

graph = {0: [1], 1: [0, 2], 2: [1, 3], 3: [2]}
print(is_bipartite(graph))

medium

A. True

B. False

C. None

D. Error

Solution

1. Step 1: Understand DFS coloring logic

   The function colors nodes 0 or 1 alternately. If a conflict occurs, it returns False.

2. Step 2: Trace the graph coloring

   Start at node 0 with color 0, node 1 gets color 1, node 2 color 0, node 3 color 1. No conflicts found.

3. Final Answer:

   True -> Option A

4. Quick Check:

   Graph is bipartite, so output is True [OK]

Hint: DFS colors nodes alternately; no conflicts means bipartite [OK]

Common Mistakes:

• Assuming graph with chain edges is not bipartite
• Confusing color assignment logic
• Ignoring disconnected nodes

4. Find the error in this bipartite check code:

def is_bipartite(graph):
    color = {}
    def dfs(node, c):
        if node in color:
            return color[node] != c
        color[node] = c
        return all(dfs(nei, 1 - c) for nei in graph[node])
    return all(dfs(node, 0) for node in graph if node not in color)

medium

A. The graph parameter should be a list, not dict

B. The color dictionary should be a list

C. The dfs function should return True unconditionally

D. The condition should be color[node] == c, not != c

Solution

1. Step 1: Analyze the color check condition

   The code returns False if a node is already colored with the same color c, so it should check equality to detect conflict.

2. Step 2: Identify the incorrect operator

   The code uses != which returns True if colors differ, which is wrong. It should be == to detect conflict and return False.

3. Final Answer:

   The condition should be color[node] == c, not != c -> Option D

4. Quick Check:

   Conflict check needs equality, not inequality [OK]

Hint: Conflict if same color found, so use == not != [OK]

Common Mistakes:

• Using != instead of == in color conflict check
• Changing color dict to list unnecessarily
• Ignoring return values in dfs

5. Given a graph with edges [(0,1), (1,2), (2,3), (3,0), (2,4)], which statement is true about its bipartite property?

hard

A. The graph is bipartite because it has no odd cycles

B. The graph is not bipartite because it contains an odd cycle

C. The graph is bipartite because it has an even cycle

D. The graph is not bipartite because it is disconnected

Solution

1. Step 1: Identify cycles in the graph

   The edges form a cycle 0-1-2-3-0 which has 4 edges (even), so no odd cycle exists.

2. Step 2: Check for odd cycles

   Since the only cycle is even length, the graph is bipartite.

3. Final Answer:

   The graph is bipartite because it has no odd cycles -> Option A

4. Quick Check:

   Odd cycle means not bipartite; no odd cycle means bipartite [OK]

Hint: Odd cycle means not bipartite; even cycle is allowed [OK]

Common Mistakes:

• Confusing even and odd cycle lengths
• Assuming disconnected means not bipartite
• Ignoring extra edges when checking cycles