Data Structures & AlgorithmsBipartite Graphs

Bipartite Graphs

LevelIntermediate

Duration60 mins

TopicBipartite Graphs

2 / 4

Two-Coloring Test

The Elegance of Coloring

Graph coloring is one of the most visually intuitive concepts in graph theory. Given a graph, we want to assign colors to vertices such that no two adjacent vertices share the same color. Finding the minimum number of colors needed (the chromatic number) is NP-hard for general graphs — but for bipartite graphs, the answer is beautifully simple: exactly two colors suffice.

This observation leads to a powerful equivalence: a graph is bipartite if and only if it can be 2-colored. This transforms the abstract question of 'can this graph be partitioned into two independent sets?' into the concrete task of 'can we assign two colors without conflicts?' And that question has an elegant, efficient answer through graph traversal.

What You Will Learn

This page provides a comprehensive exploration of the 2-coloring test for bipartiteness. You'll understand why 2-colorability and bipartiteness are equivalent, learn precisely how graph traversal achieves 2-coloring, master the algorithmic details including edge cases, and develop the ability to extend the technique to related problems.

Graph Coloring — The Foundation

Before diving into the 2-coloring test, let's establish the broader context of graph coloring. This positions bipartite detection as a special case of a fundamental and rich area of graph theory.

Definition: Proper k-Coloring

A proper k-coloring of a graph G = (V, E) is a function c: V → {1, 2, ..., k} such that for every edge (u, v) ∈ E, we have c(u) ≠ c(v). In other words: no two adjacent vertices receive the same color.

The Chromatic Number χ(G)

The chromatic number of a graph G, denoted χ(G), is the minimum k such that G admits a proper k-coloring.

χ(G) = 1 only for graphs with no edges (every vertex can be the same color)
χ(G) = 2 exactly for bipartite graphs with at least one edge
χ(G) ≥ 3 for any graph containing an odd cycle (e.g., triangles require 3 colors)

Computational Complexity:

Determining χ(G) for a general graph is NP-hard. Even asking 'is χ(G) ≤ 3?' (the 3-colorability problem) is NP-complete. However:

Asking 'is χ(G) ≤ 1?' is trivial: just check if the graph has edges.
Asking 'is χ(G) ≤ 2?' is solvable in O(V + E) — this is exactly the bipartiteness test!

This dramatic complexity difference makes the 2-coloring test both practically important and theoretically interesting — it sits at the precise boundary between 'easy' and 'hard' graph coloring problems.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// Types for graph coloring
type Color = number;  // 0, 1, 2, ... for k-coloring
 
interface ColoringResult {
  isColorable: boolean;
  coloring: Map<number, Color>;  // vertex -> assigned color
  conflictEdge?: [number, number];  // edge that caused failure
}
 
// Check if a given coloring is valid (proper)
function isProperColoring(
  graph: Map<number, number[]>,
  coloring: Map<number, Color>
): boolean {
  for (const [vertex, neighbors] of graph) {
    const vertexColor = coloring.get(vertex);
    for (const neighbor of neighbors) {
      const neighborColor = coloring.get(neighbor);
      // Adjacent vertices must have different colors
      if (vertexColor === neighborColor) {
        return false;  // Conflict!
      }
    }
  }
  return true;
}
 
// The k-coloring decision problem
function canColorWithKColors(graph: Map<number, number[]>, k: number): boolean {
  if (k === 0) return graph.size === 0;
  if (k === 1) return [...graph.values()].every(neighbors => neighbors.length === 0);
  if (k === 2) return isBipartite(graph);  // ← This is what we're learning!
  // For k >= 3: NP-complete! (requires backtracking or advanced techniques)
  return solveKColoringNPHard(graph, k);
}
 
// Placeholder - actual implementation would use backtracking
function solveKColoringNPHard(graph: Map<number, number[]>, k: number): boolean {
  // This is NP-hard for k >= 3
  throw new Error("NP-hard: exponential time required");
}
 
function isBipartite(graph: Map<number, number[]>): boolean {
  // We'll implement this properly!
  return true;  // placeholder
}

The Bipartiteness Sweet Spot

The 2-coloring test is special because it sits at the exact computational boundary: 1-colorability is trivial, 2-colorability is linear time, and k-colorability for k ≥ 3 is NP-complete. Understanding this helps appreciate both the power and limitations of efficient graph algorithms.

The Equivalence: Bipartite ⟺ 2-Colorable

The central theorem underlying the 2-coloring test establishes that bipartiteness and 2-colorability are logically equivalent. This isn't just a convenient fact — it's the deep connection that makes efficient detection possible.

Theorem: Bipartiteness Equivalence

For any graph G, the following are equivalent:

G is bipartite (vertices can be partitioned into two independent sets)
G is 2-colorable (admits a proper 2-coloring)
G contains no odd cycles

Proof of (1) ⟺ (2):

This equivalence is almost definitional once you see it:

(1) ⟹ (2): If G is bipartite with partition (U, W):

Assign color 0 to all vertices in U
Assign color 1 to all vertices in W
Every edge connects U to W, so every edge connects colors 0 and 1
This is a valid 2-coloring ✓

(2) ⟹ (1): If G has a proper 2-coloring c:

Let U = {v : c(v) = 0} (all vertices colored 0)
Let W = {v : c(v) = 1} (all vertices colored 1)
U ∩ W = ∅ (each vertex has exactly one color)
U ∪ W = V (every vertex is colored)
For any edge (u, v): c(u) ≠ c(v), so one is in U and one is in W
This is a valid bipartition ✓

The colors literally ARE the partitions!

Proof of (2) ⟺ (3):

(2) ⟹ (3): (No odd cycles if 2-colorable)

Suppose G is 2-colorable with coloring c. Consider any cycle v₁ → v₂ → ... → vₖ → v₁.

Since c is proper: c(v₁) ≠ c(v₂) ≠ c(v₃) ≠ ... ≠ c(vₖ) ≠ c(v₁)
With only 2 colors, the sequence must alternate: 0, 1, 0, 1, 0, 1, ...
After k steps, we return to v₁, so c(vₖ) ≠ c(v₁)
For the alternation to work out: k must be even
Thus, every cycle has even length (no odd cycles) ✓

(3) ⟹ (2): (2-colorable if no odd cycles)

This is the constructive proof that yields our algorithm:

For each connected component, pick any vertex v and assign color 0
Use BFS/DFS to explore from v
Assign color 1 to all neighbors of color-0 vertices
Assign color 0 to all neighbors of color-1 vertices
If we ever encounter a neighbor already colored the SAME as the current vertex → we've found an odd cycle (contradiction)
If no conflicts arise → 2-coloring is complete ✓

The key insight: if no odd cycles exist, this process cannot produce a conflict.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
Consider a triangle (3-cycle):
 
      A
     ╱ ╲
    B───C
 
Attempt to 2-color:
- Start: color A = 0
- A's neighbor B: must be ≠ 0, so B = 1
- B's neighbor C: must be ≠ 1, so C = 0
- C's neighbor A: must be ≠ 0... but A is already 0!
 
CONFLICT! The cycle has odd length (3), so we loop back
to the starting color. No valid 2-coloring exists.
 
---
 
Compare with a square (4-cycle):
 
    A───B
    │   │
    D───C
 
Attempt to 2-color:
- Start: color A = 0
- A's neighbor B: B = 1
- B's neighbor C: C = 0
- C's neighbor D: D = 1
- D's neighbor A: A should be ≠ 1... and A IS 0 ✓
 
SUCCESS! Even-length cycle, coloring alternates and matches up.

The Three-Way Equivalence

Remember: Bipartite = 2-Colorable = No Odd Cycles. Any of these three characterizations can be used to reason about or test bipartiteness. Algorithms exploit the 2-coloring view, proofs often use the odd cycle view, and applications think in terms of bipartition.

The 2-Coloring Algorithm — Complete Implementation

Now we translate the theoretical equivalence into a precise algorithm. The core idea is simple: traverse the graph, alternate colors, and detect conflicts. The implementation must handle all edge cases correctly.

Algorithm Specification

Input: Graph G = (V, E) represented as an adjacency list Output: Either a valid 2-coloring (partition), or a certificate that G is not bipartite (an odd cycle) Time Complexity: O(V + E) Space Complexity: O(V) for coloring array, O(V) for traversal queue/stack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
interface BipartiteResult {
  isBipartite: boolean;
  partition?: {
    setU: number[];  // Color 0 vertices
    setW: number[];  // Color 1 vertices
  };
  oddCycle?: number[];  // Witness if not bipartite
}
 
function checkBipartite(
  graph: Map<number, number[]>,
  n: number
): BipartiteResult {
  // Color array: -1 = unvisited, 0 = color 0, 1 = color 1
  const color: number[] = new Array(n).fill(-1);
  // Parent tracking for odd cycle reconstruction
  const parent: number[] = new Array(n).fill(-1);
  
  // Process each connected component
  for (let start = 0; start < n; start++) {
    if (color[start] !== -1) continue;  // Already visited
    
    // BFS from this unvisited vertex
    const queue: number[] = [start];
    color[start] = 0;  // Arbitrarily assign color 0 to start
    
    while (queue.length > 0) {
      const u = queue.shift()!;
      const neighbors = graph.get(u) || [];
      
      for (const v of neighbors) {
        if (color[v] === -1) {
          // Unvisited: assign opposite color
          color[v] = 1 - color[u];
          parent[v] = u;
          queue.push(v);
        } else if (color[v] === color[u]) {
          // CONFLICT! Same color as current vertex
          // This means we found an odd cycle
          const oddCycle = reconstructOddCycle(u, v, parent);
          return {
            isBipartite: false,
            oddCycle,
          };
        }
        // If color[v] !== color[u], that's expected (different colors)
      }
    }
  }
  
  // No conflicts found: graph is bipartite
  const setU: number[] = [];
  const setW: number[] = [];
  
  for (let v = 0; v < n; v++) {
    if (color[v] === 0) setU.push(v);
    else if (color[v] === 1) setW.push(v);
    // Note: isolated vertices get color 0 when visited as start
  }
  
  return {
    isBipartite: true,
    partition: { setU, setW },
  };
}
 
function reconstructOddCycle(
  u: number,
  v: number,
  parent: number[]
): number[] {
  // u and v are same-color neighbors, connected by edge (u, v)
  // They share a common ancestor in the BFS tree
  // The odd cycle is: path(u → ancestor) + path(ancestor → v) + edge(v, u)
  
  // Find paths to root for both vertices
  const pathU: number[] = [];
  const pathV: number[] = [];
  const visitedByU = new Set<number>();
  
  let curr = u;
  while (curr !== -1) {
    pathU.push(curr);
    visitedByU.add(curr);
    curr = parent[curr];
  }
  
  curr = v;
  while (curr !== -1) {
    pathV.push(curr);
    curr = parent[curr];
  }
  
  // Find lowest common ancestor (LCA)
  let lca = -1;
  for (const node of pathV) {
    if (visitedByU.has(node)) {
      lca = node;
      break;
    }
  }
  
  // Build cycle: u → lca → v → u
  const cycle: number[] = [];
  
  // u to lca
  for (const node of pathU) {
    cycle.push(node);
    if (node === lca) break;
  }
  
  // lca to v (reversed)
  const lcaToV: number[] = [];
  for (const node of pathV) {
    if (node === lca) break;
    lcaToV.push(node);
  }
  cycle.push(...lcaToV.reverse());
  
  return cycle;
}

Algorithm Walkthrough:

Step 1: Initialize

Create a color array of size V, all set to -1 (unvisited)
Create a parent array for cycle reconstruction if needed

Step 2: Process Each Component

For each unvisited vertex (color = -1), start a BFS
Assign the starting vertex color 0

Step 3: BFS With Coloring

Dequeue a vertex u
For each neighbor v of u:
- If v is unvisited: assign color = 1 - color[u] and enqueue
- If v has same color as u: CONFLICT! Return non-bipartite
- If v has opposite color: expected, continue

Step 4: Collect Partitions

After processing all components without conflict
Separate vertices by color into sets U and W

Step 5: Return Result

If successful: return the bipartition
If conflict: reconstruct and return the odd cycle

Why BFS Works Better for Visualization

While both BFS and DFS can perform 2-coloring, BFS provides an intuitive 'wave' of colors: level 0 gets color 0, level 1 gets color 1, level 2 gets color 0, and so on. This makes the algorithm's behavior easier to visualize and debug.

Step-by-Step Execution Trace

Let's trace the algorithm on two examples: one bipartite graph and one non-bipartite graph. Following the exact execution helps build intuition for how the algorithm discovers structure.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
Graph Structure (a 'house' shape with extra connections):
 
    0 ────── 1
    │╲      ╱│
    │ ╲    ╱ │
    │  ╲  ╱  │
    │   ╲╱   │
    3 ───╳─── 2
        ╱╲
       ╱  ╲
      4 ── 5
 
Adjacency List:
  0: [1, 2, 3]
  1: [0, 2]
  2: [0, 1, 3, 4, 5]
  3: [0, 2]
  4: [2, 5]
  5: [2, 4]
 
Execution Trace:
┌─────────┬─────────────────────────────────────────────────────┐
│ Step    │ Action                                              │
├─────────┼─────────────────────────────────────────────────────┤
│ Init    │ color = [-1,-1,-1,-1,-1,-1], parent = [-1,...]      │
│         │ Queue = [], start component from vertex 0           │
├─────────┼─────────────────────────────────────────────────────┤
│ 1       │ Start at 0, color[0] = 0, Queue = [0]               │
├─────────┼─────────────────────────────────────────────────────┤
│ 2       │ Dequeue 0. Neighbors: 1, 2, 3                       │
│         │   1: unvisited → color[1] = 1, parent[1] = 0        │
│         │   2: unvisited → color[2] = 1, parent[2] = 0        │
│         │   3: unvisited → color[3] = 1, parent[3] = 0        │
│         │ Queue = [1, 2, 3]                                   │
├─────────┼─────────────────────────────────────────────────────┤
│ 3       │ Dequeue 1. Neighbors: 0, 2                          │
│         │   0: color=0 ≠ color[1]=1 ✓ (expected)              │
│         │   2: color=1 ≠ color[1]=1? NO! Same color!          │
│         │                                                     │
│         │ Wait... let me check: color[2] = 1, color[1] = 1    │
│         │ They are SAME color! CONFLICT!... But wait...       │
│         │ Edge (1,2) connects color 1 to color 1 → CONFLICT!  │
└─────────┴─────────────────────────────────────────────────────┘
 
Hmm, this graph is NOT bipartite! Let me redraw to understand:
 
    0 ────── 1
    │        │
    │        │
    3        2
 
If we have edges: 0-1, 0-3, and 1-2, that's a path: 3-0-1-2. Bipartite.
But if we ALSO have 0-2, that creates triangle 0-1-2. NOT bipartite!
 
Let me use a correct bipartite example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
Graph: A simple bipartite graph with two components
 
Component 1:           Component 2:
    0 ─── 1              4 ─── 5
    │     │              
    2 ─── 3              
 
Adjacency List:
  0: [1, 2]
  1: [0, 3]
  2: [0, 3]
  3: [1, 2]
  4: [5]
  5: [4]
 
Execution Trace:
┌─────────┬─────────────────────────────────────────────────────┐
│ Step    │ Action                                              │
├─────────┼─────────────────────────────────────────────────────┤
│ Init    │ color = [-1,-1,-1,-1,-1,-1], parent = [-1,...]      │
├─────────┼─────────────────────────────────────────────────────┤
│ 1       │ Vertex 0 unvisited. color[0] = 0, Queue = [0]       │
├─────────┼─────────────────────────────────────────────────────┤
│ 2       │ Dequeue 0. Neighbors: 1, 2                          │
│         │   1: unvisited → color[1] = 1, Queue = [1]          │
│         │   2: unvisited → color[2] = 1, Queue = [1, 2]       │
├─────────┼─────────────────────────────────────────────────────┤
│ 3       │ Dequeue 1. Neighbors: 0, 3                          │
│         │   0: color=0 ≠ color[1]=1 ✓ (OK, different colors)  │
│         │   3: unvisited → color[3] = 0, Queue = [2, 3]       │
├─────────┼─────────────────────────────────────────────────────┤
│ 4       │ Dequeue 2. Neighbors: 0, 3                          │
│         │   0: color=0 ≠ color[2]=1 ✓                         │
│         │   3: color=0 ≠ color[2]=1 ✓                         │
│         │ Queue = [3]                                         │
├─────────┼─────────────────────────────────────────────────────┤
│ 5       │ Dequeue 3. Neighbors: 1, 2                          │
│         │   1: color=1 ≠ color[3]=0 ✓                         │
│         │   2: color=1 ≠ color[3]=0 ✓                         │
│         │ Queue = [] (Component 1 done)                       │
├─────────┼─────────────────────────────────────────────────────┤
│ 6       │ Check next unvisited: vertex 4                      │
│         │ color[4] = 0, Queue = [4]                           │
├─────────┼─────────────────────────────────────────────────────┤
│ 7       │ Dequeue 4. Neighbors: 5                             │
│         │   5: unvisited → color[5] = 1, Queue = [5]          │
├─────────┼─────────────────────────────────────────────────────┤
│ 8       │ Dequeue 5. Neighbors: 4                             │
│         │   4: color=0 ≠ color[5]=1 ✓                         │
│         │ Queue = [] (Component 2 done)                       │
├─────────┼─────────────────────────────────────────────────────┤
│ Done    │ All vertices processed. No conflicts!               │
│         │ Result: Bipartite                                   │
│         │ Set U (color 0): {0, 3, 4}                          │
│         │ Set W (color 1): {1, 2, 5}                          │
└─────────┴─────────────────────────────────────────────────────┘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
Graph: A triangle (simplest non-bipartite graph)
 
        0
       ╱ ╲
      ╱   ╲
     1 ─── 2
 
Adjacency List:
  0: [1, 2]
  1: [0, 2]
  2: [0, 1]
 
Execution Trace:
┌─────────┬─────────────────────────────────────────────────────┐
│ Step    │ Action                                              │
├─────────┼─────────────────────────────────────────────────────┤
│ Init    │ color = [-1,-1,-1], parent = [-1,-1,-1]             │
├─────────┼─────────────────────────────────────────────────────┤
│ 1       │ Vertex 0 unvisited. color[0] = 0, Queue = [0]       │
├─────────┼─────────────────────────────────────────────────────┤
│ 2       │ Dequeue 0. Neighbors: 1, 2                          │
│         │   1: unvisited → color[1] = 1, parent[1] = 0        │
│         │   2: unvisited → color[2] = 1, parent[2] = 0        │
│         │ Queue = [1, 2]                                      │
├─────────┼─────────────────────────────────────────────────────┤
│ 3       │ Dequeue 1. Neighbors: 0, 2                          │
│         │   0: color=0 ≠ color[1]=1 ✓                         │
│         │   2: color=1 == color[1]=1 ✗ CONFLICT!              │
│         │                                                     │
│         │ ⚠️ Same-color neighbors detected!                   │
│         │ Edge (1, 2) connects two color-1 vertices.          │
└─────────┴─────────────────────────────────────────────────────┘
 
RESULT: Not bipartite!
 
Odd Cycle Reconstruction:
- Conflict at edge (1, 2), both have color 1
- Parent[1] = 0, Parent[2] = 0
- Common ancestor: 0
- Cycle: 1 → 0 → 2 → 1 (length 3 = ODD)
 
The algorithm correctly identifies the triangle as an odd cycle.

Key Observation

Notice that the conflict is detected as soon as we try to process an edge where both endpoints have the same color. We don't need to complete the traversal — early termination saves time when non-bipartiteness is detected.

Correctness Analysis — Why It Always Works

Let's rigorously prove that the 2-coloring algorithm is correct. This means establishing two properties:

Soundness: If the algorithm returns 'bipartite,' the graph truly is bipartite.
Completeness: If the graph is bipartite, the algorithm will correctly identify it.

These together ensure the algorithm never gives wrong answers.

Proof of Soundness:

Suppose the algorithm returns 'bipartite' with partition (U, W).

Claim: Every edge in the graph connects a vertex in U to a vertex in W.

Proof: Consider any edge (u, v) in the graph.

During BFS, one of {u, v} was discovered before the other.
Say u was discovered first, and v was discovered from u.
At that moment, the algorithm set color[v] = 1 - color[u].
Therefore, color[u] ≠ color[v].
If u has color 0 (in U), then v has color 1 (in W), or vice versa.
Thus, edge (u, v) crosses between U and W. ✓

Wait, what about edges where both vertices were discovered independently?

This can happen in disconnected graphs, where u and v are in different components. But then there's no edge between them (since they're in different components). Every edge within a component is properly colored as shown above. ✓

Proof of Completeness:

Suppose the graph is bipartite with some partition (U, W).

Claim: The algorithm will not find a conflict.

Proof: Consider the 2-coloring produced by the algorithm.

Fix any connected component and the algorithm's starting vertex v₀.
The BFS assigns colors by distance: all vertices at even distance from v₀ get color 0, odd distance get color 1.
Now, consider any two adjacent vertices u, w in the graph.
Since the graph is bipartite, one is in U and one is in W (by definition).
Moving from U to W or W to U changes parity of distance by 1.
Therefore, u and w have different distances mod 2 from v₀.
Therefore, color[u] ≠ color[w].
No conflict can arise. ✓

Key insight: The algorithm's coloring may differ from the 'true' partition by swapping colors, but it's always a valid 2-coloring.

The Contrapositive Perspective

Completeness can also be proved by contrapositive: If the algorithm finds a conflict, then the graph is not bipartite. This is because a conflict implies two same-colored neighbors, which means an edge whose endpoints are at the same distance parity from the start. This can only happen if there's an odd cycle.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
// INVARIANT maintained throughout BFS:
// For every vertex v that has been colored:
//   color[v] = distance(start, v) % 2
//
// This invariant ensures:
// 1. Adjacent vertices have different colors (distances differ by 1)
// 2. The coloring is consistent across the component
 
function checkBipartiteWithInvariant(
  graph: Map<number, number[]>,
  n: number
): boolean {
  const color: number[] = new Array(n).fill(-1);
  const distance: number[] = new Array(n).fill(-1);
  
  for (let start = 0; start < n; start++) {
    if (color[start] !== -1) continue;
    
    const queue: number[] = [start];
    color[start] = 0;
    distance[start] = 0;
    
    while (queue.length > 0) {
      const u = queue.shift()!;
      
      // INVARIANT CHECK: color[u] should equal distance[u] % 2
      console.assert(
        color[u] === distance[u] % 2,
        `Invariant violated at vertex ${u}`
      );
      
      for (const v of graph.get(u) || []) {
        if (color[v] === -1) {
          distance[v] = distance[u] + 1;
          color[v] = distance[v] % 2;  // Equivalent to: 1 - color[u]
          queue.push(v);
        } else if (color[v] === color[u]) {
          // Conflict: same color means same distance parity
          // But adjacent vertices should have distance differing by 1
          // This implies an odd cycle exists
          return false;
        }
      }
    }
  }
  
  return true;
}

Edge Cases and Implementation Robustness

A robust implementation must handle various edge cases correctly. Let's enumerate them and ensure our algorithm addresses each one:

Edge Cases for 2-Coloring Algorithm
Case	Description	Expected Result	Implementation Note
Empty graph	n = 0, no vertices	Bipartite (vacuously)	Return true with empty partitions
Single vertex	n = 1, no edges	Bipartite	One vertex in U, empty W (or assign to W)
No edges	n vertices, 0 edges	Bipartite	Any partition works
Disconnected	Multiple components	Check each component	Outer loop handles this
Self-loop	Edge (v, v)	NOT bipartite	color[v] == color[v] → conflict
Parallel edges	Multiple edges (u, v)	Same as single edge	Extra edges don't cause new conflicts
Complete bipartite	K_{m,n}	Bipartite	All edges cross partitions
Complete graph	K_n (n ≥ 3)	NOT bipartite	Contains triangles
Long odd cycle	C_{2k+1}	NOT bipartite	Detected when cycle closes
Long even cycle	C_{2k}	Bipartite	Coloring alternates correctly

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
interface RobustBipartiteResult {
  isBipartite: boolean;
  partition: { setU: number[]; setW: number[] } | null;
  oddCycle: number[] | null;
  stats: {
    numVertices: number;
    numEdges: number;
    numComponents: number;
    hasSelfLoops: boolean;
  };
}
 
function robustBipartiteCheck(
  adjacencyList: Map<number, number[]>,
  n: number
): RobustBipartiteResult {
  // Handle empty graph
  if (n === 0) {
    return {
      isBipartite: true,
      partition: { setU: [], setW: [] },
      oddCycle: null,
      stats: { numVertices: 0, numEdges: 0, numComponents: 0, hasSelfLoops: false },
    };
  }
  
  const color: number[] = new Array(n).fill(-1);
  const parent: number[] = new Array(n).fill(-1);
  
  let numComponents = 0;
  let hasSelfLoops = false;
  let edgeCount = 0;
  
  for (let start = 0; start < n; start++) {
    if (color[start] !== -1) continue;
    
    numComponents++;
    const queue: number[] = [start];
    color[start] = 0;
    
    while (queue.length > 0) {
      const u = queue.shift()!;
      const neighbors = adjacencyList.get(u) || [];
      
      for (const v of neighbors) {
        // Count edges (each edge counted twice in undirected, so divide later)
        edgeCount++;
        
        // Check for self-loop
        if (u === v) {
          hasSelfLoops = true;
          // Self-loop is an odd cycle of length 1
          return {
            isBipartite: false,
            partition: null,
            oddCycle: [u],  // Self-loop at u
            stats: { numVertices: n, numEdges: edgeCount / 2, numComponents, hasSelfLoops: true },
          };
        }
        
        if (color[v] === -1) {
          color[v] = 1 - color[u];
          parent[v] = u;
          queue.push(v);
        } else if (color[v] === color[u]) {
          // Found odd cycle
          const oddCycle = reconstructCycle(u, v, parent);
          return {
            isBipartite: false,
            partition: null,
            oddCycle,
            stats: { numVertices: n, numEdges: edgeCount / 2, numComponents, hasSelfLoops },
          };
        }
      }
    }
  }
  
  // Build partition
  const setU: number[] = [];
  const setW: number[] = [];
  for (let v = 0; v < n; v++) {
    if (color[v] === 0) setU.push(v);
    else setW.push(v);
  }
  
  return {
    isBipartite: true,
    partition: { setU, setW },
    oddCycle: null,
    stats: { numVertices: n, numEdges: edgeCount / 2, numComponents, hasSelfLoops },
  };
}
 
function reconstructCycle(u: number, v: number, parent: number[]): number[] {
  // Same as before - find LCA and build cycle path
  const pathU: number[] = [];
  const visitedByU = new Set<number>();
  
  let curr = u;
  while (curr !== -1) {
    pathU.push(curr);
    visitedByU.add(curr);
    curr = parent[curr];
  }
  
  let lca = -1;
  const pathV: number[] = [];
  curr = v;
  while (curr !== -1) {
    pathV.push(curr);
    if (visitedByU.has(curr)) {
      lca = curr;
      break;
    }
    curr = parent[curr];
  }
  
  const cycle: number[] = [];
  for (const node of pathU) {
    cycle.push(node);
    if (node === lca) break;
  }
  
  const vSide: number[] = [];
  for (const node of pathV) {
    if (node === lca) break;
    vSide.push(node);
  }
  cycle.push(...vSide.reverse());
  
  return cycle;
}

Self-Loops Are Special

Self-loops immediately disqualify a graph from being bipartite. They're often forgotten in implementations but represent the simplest case of an 'odd cycle' (length 1). Always check u === v when processing neighbor edges.

Summary: The Two-Coloring Test

The 2-coloring test is an elegant fusion of graph theory and algorithmic technique. Let's summarize the key insights:

Key Takeaways

•Equivalence Theorem — A graph is bipartite ⟺ it's 2-colorable ⟺ it has no odd cycles. This three-way equivalence is fundamental.
•Algorithm Insight — The 2-coloring algorithm leverages BFS/DFS to assign alternating colors. Conflicts reveal odd cycles.
•Complexity Boundary — 2-colorability is solvable in O(V + E), while 3-colorability is NP-complete. Bipartiteness sits at the tractability boundary.
•Constructive Results — The algorithm doesn't just answer yes/no; it produces the actual partition (if bipartite) or an odd cycle witness (if not).
•Correctness Proof — Soundness and completeness follow from the invariant that color equals distance parity.
•Edge Case Handling — Self-loops, disconnected graphs, empty graphs, and single vertices all require explicit handling.

What's Next:

With the theoretical foundation of 2-coloring established, the next page explores the practical implementation using BFS and DFS traversals. We'll examine both approaches in depth, compare their characteristics, and provide production-ready code with comprehensive testing strategies.

Theory Mastered

You now understand the deep theoretical connection between bipartiteness and 2-colorability. This foundation enables you to reason about algorithm correctness and extend the technique to related problems like weighted bipartite matching and graph augmentation.

2 / 4

Loading learning content...

Data Structures & AlgorithmsBipartite Graphs

Bipartite Graphs

LevelIntermediate

Duration60 mins

TopicBipartite Graphs

2 / 4

Two-Coloring Test

The Elegance of Coloring

What You Will Learn

Graph Coloring — The Foundation

Before diving into the 2-coloring test, let's establish the broader context of graph coloring. This positions bipartite detection as a special case of a fundamental and rich area of graph theory.

Definition: Proper k-Coloring

The Chromatic Number χ(G)

The chromatic number of a graph G, denoted χ(G), is the minimum k such that G admits a proper k-coloring.

χ(G) = 1 only for graphs with no edges (every vertex can be the same color)
χ(G) = 2 exactly for bipartite graphs with at least one edge
χ(G) ≥ 3 for any graph containing an odd cycle (e.g., triangles require 3 colors)

Computational Complexity:

Determining χ(G) for a general graph is NP-hard. Even asking 'is χ(G) ≤ 3?' (the 3-colorability problem) is NP-complete. However:

Asking 'is χ(G) ≤ 1?' is trivial: just check if the graph has edges.
Asking 'is χ(G) ≤ 2?' is solvable in O(V + E) — this is exactly the bipartiteness test!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// Types for graph coloring
type Color = number;  // 0, 1, 2, ... for k-coloring
 
interface ColoringResult {
  isColorable: boolean;
  coloring: Map<number, Color>;  // vertex -> assigned color
  conflictEdge?: [number, number];  // edge that caused failure
}
 
// Check if a given coloring is valid (proper)
function isProperColoring(
  graph: Map<number, number[]>,
  coloring: Map<number, Color>
): boolean {
  for (const [vertex, neighbors] of graph) {
    const vertexColor = coloring.get(vertex);
    for (const neighbor of neighbors) {
      const neighborColor = coloring.get(neighbor);
      // Adjacent vertices must have different colors
      if (vertexColor === neighborColor) {
        return false;  // Conflict!
      }
    }
  }
  return true;
}
 
// The k-coloring decision problem
function canColorWithKColors(graph: Map<number, number[]>, k: number): boolean {
  if (k === 0) return graph.size === 0;
  if (k === 1) return [...graph.values()].every(neighbors => neighbors.length === 0);
  if (k === 2) return isBipartite(graph);  // ← This is what we're learning!
  // For k >= 3: NP-complete! (requires backtracking or advanced techniques)
  return solveKColoringNPHard(graph, k);
}
 
// Placeholder - actual implementation would use backtracking
function solveKColoringNPHard(graph: Map<number, number[]>, k: number): boolean {
  // This is NP-hard for k >= 3
  throw new Error("NP-hard: exponential time required");
}
 
function isBipartite(graph: Map<number, number[]>): boolean {
  // We'll implement this properly!
  return true;  // placeholder
}

The Bipartiteness Sweet Spot

The Equivalence: Bipartite ⟺ 2-Colorable

Theorem: Bipartiteness Equivalence

For any graph G, the following are equivalent:

G is bipartite (vertices can be partitioned into two independent sets)
G is 2-colorable (admits a proper 2-coloring)
G contains no odd cycles

Proof of (1) ⟺ (2):

This equivalence is almost definitional once you see it:

(1) ⟹ (2): If G is bipartite with partition (U, W):

Assign color 0 to all vertices in U
Assign color 1 to all vertices in W
Every edge connects U to W, so every edge connects colors 0 and 1
This is a valid 2-coloring ✓

(2) ⟹ (1): If G has a proper 2-coloring c:

Let U = {v : c(v) = 0} (all vertices colored 0)
Let W = {v : c(v) = 1} (all vertices colored 1)
U ∩ W = ∅ (each vertex has exactly one color)
U ∪ W = V (every vertex is colored)
For any edge (u, v): c(u) ≠ c(v), so one is in U and one is in W
This is a valid bipartition ✓

The colors literally ARE the partitions!

Proof of (2) ⟺ (3):

(2) ⟹ (3): (No odd cycles if 2-colorable)

Suppose G is 2-colorable with coloring c. Consider any cycle v₁ → v₂ → ... → vₖ → v₁.

Since c is proper: c(v₁) ≠ c(v₂) ≠ c(v₃) ≠ ... ≠ c(vₖ) ≠ c(v₁)
With only 2 colors, the sequence must alternate: 0, 1, 0, 1, 0, 1, ...
After k steps, we return to v₁, so c(vₖ) ≠ c(v₁)
For the alternation to work out: k must be even
Thus, every cycle has even length (no odd cycles) ✓

(3) ⟹ (2): (2-colorable if no odd cycles)

This is the constructive proof that yields our algorithm:

For each connected component, pick any vertex v and assign color 0
Use BFS/DFS to explore from v
Assign color 1 to all neighbors of color-0 vertices
Assign color 0 to all neighbors of color-1 vertices
If we ever encounter a neighbor already colored the SAME as the current vertex → we've found an odd cycle (contradiction)
If no conflicts arise → 2-coloring is complete ✓

The key insight: if no odd cycles exist, this process cannot produce a conflict.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
Consider a triangle (3-cycle):
 
      A
     ╱ ╲
    B───C
 
Attempt to 2-color:
- Start: color A = 0
- A's neighbor B: must be ≠ 0, so B = 1
- B's neighbor C: must be ≠ 1, so C = 0
- C's neighbor A: must be ≠ 0... but A is already 0!
 
CONFLICT! The cycle has odd length (3), so we loop back
to the starting color. No valid 2-coloring exists.
 
---
 
Compare with a square (4-cycle):
 
    A───B
    │   │
    D───C
 
Attempt to 2-color:
- Start: color A = 0
- A's neighbor B: B = 1
- B's neighbor C: C = 0
- C's neighbor D: D = 1
- D's neighbor A: A should be ≠ 1... and A IS 0 ✓
 
SUCCESS! Even-length cycle, coloring alternates and matches up.

The Three-Way Equivalence

The 2-Coloring Algorithm — Complete Implementation

Algorithm Specification

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
interface BipartiteResult {
  isBipartite: boolean;
  partition?: {
    setU: number[];  // Color 0 vertices
    setW: number[];  // Color 1 vertices
  };
  oddCycle?: number[];  // Witness if not bipartite
}
 
function checkBipartite(
  graph: Map<number, number[]>,
  n: number
): BipartiteResult {
  // Color array: -1 = unvisited, 0 = color 0, 1 = color 1
  const color: number[] = new Array(n).fill(-1);
  // Parent tracking for odd cycle reconstruction
  const parent: number[] = new Array(n).fill(-1);
  
  // Process each connected component
  for (let start = 0; start < n; start++) {
    if (color[start] !== -1) continue;  // Already visited
    
    // BFS from this unvisited vertex
    const queue: number[] = [start];
    color[start] = 0;  // Arbitrarily assign color 0 to start
    
    while (queue.length > 0) {
      const u = queue.shift()!;
      const neighbors = graph.get(u) || [];
      
      for (const v of neighbors) {
        if (color[v] === -1) {
          // Unvisited: assign opposite color
          color[v] = 1 - color[u];
          parent[v] = u;
          queue.push(v);
        } else if (color[v] === color[u]) {
          // CONFLICT! Same color as current vertex
          // This means we found an odd cycle
          const oddCycle = reconstructOddCycle(u, v, parent);
          return {
            isBipartite: false,
            oddCycle,
          };
        }
        // If color[v] !== color[u], that's expected (different colors)
      }
    }
  }
  
  // No conflicts found: graph is bipartite
  const setU: number[] = [];
  const setW: number[] = [];
  
  for (let v = 0; v < n; v++) {
    if (color[v] === 0) setU.push(v);
    else if (color[v] === 1) setW.push(v);
    // Note: isolated vertices get color 0 when visited as start
  }
  
  return {
    isBipartite: true,
    partition: { setU, setW },
  };
}
 
function reconstructOddCycle(
  u: number,
  v: number,
  parent: number[]
): number[] {
  // u and v are same-color neighbors, connected by edge (u, v)
  // They share a common ancestor in the BFS tree
  // The odd cycle is: path(u → ancestor) + path(ancestor → v) + edge(v, u)
  
  // Find paths to root for both vertices
  const pathU: number[] = [];
  const pathV: number[] = [];
  const visitedByU = new Set<number>();
  
  let curr = u;
  while (curr !== -1) {
    pathU.push(curr);
    visitedByU.add(curr);
    curr = parent[curr];
  }
  
  curr = v;
  while (curr !== -1) {
    pathV.push(curr);
    curr = parent[curr];
  }
  
  // Find lowest common ancestor (LCA)
  let lca = -1;
  for (const node of pathV) {
    if (visitedByU.has(node)) {
      lca = node;
      break;
    }
  }
  
  // Build cycle: u → lca → v → u
  const cycle: number[] = [];
  
  // u to lca
  for (const node of pathU) {
    cycle.push(node);
    if (node === lca) break;
  }
  
  // lca to v (reversed)
  const lcaToV: number[] = [];
  for (const node of pathV) {
    if (node === lca) break;
    lcaToV.push(node);
  }
  cycle.push(...lcaToV.reverse());
  
  return cycle;
}

Algorithm Walkthrough:

Step 1: Initialize

Create a color array of size V, all set to -1 (unvisited)
Create a parent array for cycle reconstruction if needed

Step 2: Process Each Component

For each unvisited vertex (color = -1), start a BFS
Assign the starting vertex color 0

Step 3: BFS With Coloring

Dequeue a vertex u
For each neighbor v of u:
- If v is unvisited: assign color = 1 - color[u] and enqueue
- If v has same color as u: CONFLICT! Return non-bipartite
- If v has opposite color: expected, continue

Step 4: Collect Partitions

After processing all components without conflict
Separate vertices by color into sets U and W

Step 5: Return Result

If successful: return the bipartition
If conflict: reconstruct and return the odd cycle

Why BFS Works Better for Visualization

Step-by-Step Execution Trace

Let's trace the algorithm on two examples: one bipartite graph and one non-bipartite graph. Following the exact execution helps build intuition for how the algorithm discovers structure.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
Graph Structure (a 'house' shape with extra connections):
 
    0 ────── 1
    │╲      ╱│
    │ ╲    ╱ │
    │  ╲  ╱  │
    │   ╲╱   │
    3 ───╳─── 2
        ╱╲
       ╱  ╲
      4 ── 5
 
Adjacency List:
  0: [1, 2, 3]
  1: [0, 2]
  2: [0, 1, 3, 4, 5]
  3: [0, 2]
  4: [2, 5]
  5: [2, 4]
 
Execution Trace:
┌─────────┬─────────────────────────────────────────────────────┐
│ Step    │ Action                                              │
├─────────┼─────────────────────────────────────────────────────┤
│ Init    │ color = [-1,-1,-1,-1,-1,-1], parent = [-1,...]      │
│         │ Queue = [], start component from vertex 0           │
├─────────┼─────────────────────────────────────────────────────┤
│ 1       │ Start at 0, color[0] = 0, Queue = [0]               │
├─────────┼─────────────────────────────────────────────────────┤
│ 2       │ Dequeue 0. Neighbors: 1, 2, 3                       │
│         │   1: unvisited → color[1] = 1, parent[1] = 0        │
│         │   2: unvisited → color[2] = 1, parent[2] = 0        │
│         │   3: unvisited → color[3] = 1, parent[3] = 0        │
│         │ Queue = [1, 2, 3]                                   │
├─────────┼─────────────────────────────────────────────────────┤
│ 3       │ Dequeue 1. Neighbors: 0, 2                          │
│         │   0: color=0 ≠ color[1]=1 ✓ (expected)              │
│         │   2: color=1 ≠ color[1]=1? NO! Same color!          │
│         │                                                     │
│         │ Wait... let me check: color[2] = 1, color[1] = 1    │
│         │ They are SAME color! CONFLICT!... But wait...       │
│         │ Edge (1,2) connects color 1 to color 1 → CONFLICT!  │
└─────────┴─────────────────────────────────────────────────────┘
 
Hmm, this graph is NOT bipartite! Let me redraw to understand:
 
    0 ────── 1
    │        │
    │        │
    3        2
 
If we have edges: 0-1, 0-3, and 1-2, that's a path: 3-0-1-2. Bipartite.
But if we ALSO have 0-2, that creates triangle 0-1-2. NOT bipartite!
 
Let me use a correct bipartite example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
Graph: A simple bipartite graph with two components
 
Component 1:           Component 2:
    0 ─── 1              4 ─── 5
    │     │              
    2 ─── 3              
 
Adjacency List:
  0: [1, 2]
  1: [0, 3]
  2: [0, 3]
  3: [1, 2]
  4: [5]
  5: [4]
 
Execution Trace:
┌─────────┬─────────────────────────────────────────────────────┐
│ Step    │ Action                                              │
├─────────┼─────────────────────────────────────────────────────┤
│ Init    │ color = [-1,-1,-1,-1,-1,-1], parent = [-1,...]      │
├─────────┼─────────────────────────────────────────────────────┤
│ 1       │ Vertex 0 unvisited. color[0] = 0, Queue = [0]       │
├─────────┼─────────────────────────────────────────────────────┤
│ 2       │ Dequeue 0. Neighbors: 1, 2                          │
│         │   1: unvisited → color[1] = 1, Queue = [1]          │
│         │   2: unvisited → color[2] = 1, Queue = [1, 2]       │
├─────────┼─────────────────────────────────────────────────────┤
│ 3       │ Dequeue 1. Neighbors: 0, 3                          │
│         │   0: color=0 ≠ color[1]=1 ✓ (OK, different colors)  │
│         │   3: unvisited → color[3] = 0, Queue = [2, 3]       │
├─────────┼─────────────────────────────────────────────────────┤
│ 4       │ Dequeue 2. Neighbors: 0, 3                          │
│         │   0: color=0 ≠ color[2]=1 ✓                         │
│         │   3: color=0 ≠ color[2]=1 ✓                         │
│         │ Queue = [3]                                         │
├─────────┼─────────────────────────────────────────────────────┤
│ 5       │ Dequeue 3. Neighbors: 1, 2                          │
│         │   1: color=1 ≠ color[3]=0 ✓                         │
│         │   2: color=1 ≠ color[3]=0 ✓                         │
│         │ Queue = [] (Component 1 done)                       │
├─────────┼─────────────────────────────────────────────────────┤
│ 6       │ Check next unvisited: vertex 4                      │
│         │ color[4] = 0, Queue = [4]                           │
├─────────┼─────────────────────────────────────────────────────┤
│ 7       │ Dequeue 4. Neighbors: 5                             │
│         │   5: unvisited → color[5] = 1, Queue = [5]          │
├─────────┼─────────────────────────────────────────────────────┤
│ 8       │ Dequeue 5. Neighbors: 4                             │
│         │   4: color=0 ≠ color[5]=1 ✓                         │
│         │ Queue = [] (Component 2 done)                       │
├─────────┼─────────────────────────────────────────────────────┤
│ Done    │ All vertices processed. No conflicts!               │
│         │ Result: Bipartite                                   │
│         │ Set U (color 0): {0, 3, 4}                          │
│         │ Set W (color 1): {1, 2, 5}                          │
└─────────┴─────────────────────────────────────────────────────┘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
Graph: A triangle (simplest non-bipartite graph)
 
        0
       ╱ ╲
      ╱   ╲
     1 ─── 2
 
Adjacency List:
  0: [1, 2]
  1: [0, 2]
  2: [0, 1]
 
Execution Trace:
┌─────────┬─────────────────────────────────────────────────────┐
│ Step    │ Action                                              │
├─────────┼─────────────────────────────────────────────────────┤
│ Init    │ color = [-1,-1,-1], parent = [-1,-1,-1]             │
├─────────┼─────────────────────────────────────────────────────┤
│ 1       │ Vertex 0 unvisited. color[0] = 0, Queue = [0]       │
├─────────┼─────────────────────────────────────────────────────┤
│ 2       │ Dequeue 0. Neighbors: 1, 2                          │
│         │   1: unvisited → color[1] = 1, parent[1] = 0        │
│         │   2: unvisited → color[2] = 1, parent[2] = 0        │
│         │ Queue = [1, 2]                                      │
├─────────┼─────────────────────────────────────────────────────┤
│ 3       │ Dequeue 1. Neighbors: 0, 2                          │
│         │   0: color=0 ≠ color[1]=1 ✓                         │
│         │   2: color=1 == color[1]=1 ✗ CONFLICT!              │
│         │                                                     │
│         │ ⚠️ Same-color neighbors detected!                   │
│         │ Edge (1, 2) connects two color-1 vertices.          │
└─────────┴─────────────────────────────────────────────────────┘
 
RESULT: Not bipartite!
 
Odd Cycle Reconstruction:
- Conflict at edge (1, 2), both have color 1
- Parent[1] = 0, Parent[2] = 0
- Common ancestor: 0
- Cycle: 1 → 0 → 2 → 1 (length 3 = ODD)
 
The algorithm correctly identifies the triangle as an odd cycle.

Key Observation

Correctness Analysis — Why It Always Works

Let's rigorously prove that the 2-coloring algorithm is correct. This means establishing two properties:

Soundness: If the algorithm returns 'bipartite,' the graph truly is bipartite.
Completeness: If the graph is bipartite, the algorithm will correctly identify it.

These together ensure the algorithm never gives wrong answers.

Proof of Soundness:

Suppose the algorithm returns 'bipartite' with partition (U, W).

Claim: Every edge in the graph connects a vertex in U to a vertex in W.

Proof: Consider any edge (u, v) in the graph.

During BFS, one of {u, v} was discovered before the other.
Say u was discovered first, and v was discovered from u.
At that moment, the algorithm set color[v] = 1 - color[u].
Therefore, color[u] ≠ color[v].
If u has color 0 (in U), then v has color 1 (in W), or vice versa.
Thus, edge (u, v) crosses between U and W. ✓

Wait, what about edges where both vertices were discovered independently?

Proof of Completeness:

Suppose the graph is bipartite with some partition (U, W).

Claim: The algorithm will not find a conflict.

Proof: Consider the 2-coloring produced by the algorithm.

Fix any connected component and the algorithm's starting vertex v₀.
The BFS assigns colors by distance: all vertices at even distance from v₀ get color 0, odd distance get color 1.
Now, consider any two adjacent vertices u, w in the graph.
Since the graph is bipartite, one is in U and one is in W (by definition).
Moving from U to W or W to U changes parity of distance by 1.
Therefore, u and w have different distances mod 2 from v₀.
Therefore, color[u] ≠ color[w].
No conflict can arise. ✓

Key insight: The algorithm's coloring may differ from the 'true' partition by swapping colors, but it's always a valid 2-coloring.

The Contrapositive Perspective

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
// INVARIANT maintained throughout BFS:
// For every vertex v that has been colored:
//   color[v] = distance(start, v) % 2
//
// This invariant ensures:
// 1. Adjacent vertices have different colors (distances differ by 1)
// 2. The coloring is consistent across the component
 
function checkBipartiteWithInvariant(
  graph: Map<number, number[]>,
  n: number
): boolean {
  const color: number[] = new Array(n).fill(-1);
  const distance: number[] = new Array(n).fill(-1);
  
  for (let start = 0; start < n; start++) {
    if (color[start] !== -1) continue;
    
    const queue: number[] = [start];
    color[start] = 0;
    distance[start] = 0;
    
    while (queue.length > 0) {
      const u = queue.shift()!;
      
      // INVARIANT CHECK: color[u] should equal distance[u] % 2
      console.assert(
        color[u] === distance[u] % 2,
        `Invariant violated at vertex ${u}`
      );
      
      for (const v of graph.get(u) || []) {
        if (color[v] === -1) {
          distance[v] = distance[u] + 1;
          color[v] = distance[v] % 2;  // Equivalent to: 1 - color[u]
          queue.push(v);
        } else if (color[v] === color[u]) {
          // Conflict: same color means same distance parity
          // But adjacent vertices should have distance differing by 1
          // This implies an odd cycle exists
          return false;
        }
      }
    }
  }
  
  return true;
}

Edge Cases and Implementation Robustness

A robust implementation must handle various edge cases correctly. Let's enumerate them and ensure our algorithm addresses each one:

Edge Cases for 2-Coloring Algorithm
Case	Description	Expected Result	Implementation Note
Empty graph	n = 0, no vertices	Bipartite (vacuously)	Return true with empty partitions
Single vertex	n = 1, no edges	Bipartite	One vertex in U, empty W (or assign to W)
No edges	n vertices, 0 edges	Bipartite	Any partition works
Disconnected	Multiple components	Check each component	Outer loop handles this
Self-loop	Edge (v, v)	NOT bipartite	color[v] == color[v] → conflict
Parallel edges	Multiple edges (u, v)	Same as single edge	Extra edges don't cause new conflicts
Complete bipartite	K_{m,n}	Bipartite	All edges cross partitions
Complete graph	K_n (n ≥ 3)	NOT bipartite	Contains triangles
Long odd cycle	C_{2k+1}	NOT bipartite	Detected when cycle closes
Long even cycle	C_{2k}	Bipartite	Coloring alternates correctly

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
interface RobustBipartiteResult {
  isBipartite: boolean;
  partition: { setU: number[]; setW: number[] } | null;
  oddCycle: number[] | null;
  stats: {
    numVertices: number;
    numEdges: number;
    numComponents: number;
    hasSelfLoops: boolean;
  };
}
 
function robustBipartiteCheck(
  adjacencyList: Map<number, number[]>,
  n: number
): RobustBipartiteResult {
  // Handle empty graph
  if (n === 0) {
    return {
      isBipartite: true,
      partition: { setU: [], setW: [] },
      oddCycle: null,
      stats: { numVertices: 0, numEdges: 0, numComponents: 0, hasSelfLoops: false },
    };
  }
  
  const color: number[] = new Array(n).fill(-1);
  const parent: number[] = new Array(n).fill(-1);
  
  let numComponents = 0;
  let hasSelfLoops = false;
  let edgeCount = 0;
  
  for (let start = 0; start < n; start++) {
    if (color[start] !== -1) continue;
    
    numComponents++;
    const queue: number[] = [start];
    color[start] = 0;
    
    while (queue.length > 0) {
      const u = queue.shift()!;
      const neighbors = adjacencyList.get(u) || [];
      
      for (const v of neighbors) {
        // Count edges (each edge counted twice in undirected, so divide later)
        edgeCount++;
        
        // Check for self-loop
        if (u === v) {
          hasSelfLoops = true;
          // Self-loop is an odd cycle of length 1
          return {
            isBipartite: false,
            partition: null,
            oddCycle: [u],  // Self-loop at u
            stats: { numVertices: n, numEdges: edgeCount / 2, numComponents, hasSelfLoops: true },
          };
        }
        
        if (color[v] === -1) {
          color[v] = 1 - color[u];
          parent[v] = u;
          queue.push(v);
        } else if (color[v] === color[u]) {
          // Found odd cycle
          const oddCycle = reconstructCycle(u, v, parent);
          return {
            isBipartite: false,
            partition: null,
            oddCycle,
            stats: { numVertices: n, numEdges: edgeCount / 2, numComponents, hasSelfLoops },
          };
        }
      }
    }
  }
  
  // Build partition
  const setU: number[] = [];
  const setW: number[] = [];
  for (let v = 0; v < n; v++) {
    if (color[v] === 0) setU.push(v);
    else setW.push(v);
  }
  
  return {
    isBipartite: true,
    partition: { setU, setW },
    oddCycle: null,
    stats: { numVertices: n, numEdges: edgeCount / 2, numComponents, hasSelfLoops },
  };
}
 
function reconstructCycle(u: number, v: number, parent: number[]): number[] {
  // Same as before - find LCA and build cycle path
  const pathU: number[] = [];
  const visitedByU = new Set<number>();
  
  let curr = u;
  while (curr !== -1) {
    pathU.push(curr);
    visitedByU.add(curr);
    curr = parent[curr];
  }
  
  let lca = -1;
  const pathV: number[] = [];
  curr = v;
  while (curr !== -1) {
    pathV.push(curr);
    if (visitedByU.has(curr)) {
      lca = curr;
      break;
    }
    curr = parent[curr];
  }
  
  const cycle: number[] = [];
  for (const node of pathU) {
    cycle.push(node);
    if (node === lca) break;
  }
  
  const vSide: number[] = [];
  for (const node of pathV) {
    if (node === lca) break;
    vSide.push(node);
  }
  cycle.push(...vSide.reverse());
  
  return cycle;
}

Self-Loops Are Special

Summary: The Two-Coloring Test

The 2-coloring test is an elegant fusion of graph theory and algorithmic technique. Let's summarize the key insights:

Key Takeaways

•Equivalence Theorem — A graph is bipartite ⟺ it's 2-colorable ⟺ it has no odd cycles. This three-way equivalence is fundamental.
•Algorithm Insight — The 2-coloring algorithm leverages BFS/DFS to assign alternating colors. Conflicts reveal odd cycles.
•Complexity Boundary — 2-colorability is solvable in O(V + E), while 3-colorability is NP-complete. Bipartiteness sits at the tractability boundary.
•Constructive Results — The algorithm doesn't just answer yes/no; it produces the actual partition (if bipartite) or an odd cycle witness (if not).
•Correctness Proof — Soundness and completeness follow from the invariant that color equals distance parity.
•Edge Case Handling — Self-loops, disconnected graphs, empty graphs, and single vertices all require explicit handling.

What's Next:

Theory Mastered

2 / 4