Bipartite Graphs - Learning Module

Loading content...

0/276

BFS/DFS-Based Detection

Two Paths to the Same Truth

The theoretical foundation is clear: a graph is bipartite if and only if we can 2-color it. But how should we traverse the graph to attempt this coloring? Graph theory offers two fundamental strategies: Breadth-First Search (BFS) explores level by level, while Depth-First Search (DFS) plunges deep before backtracking.

Both approaches work for bipartite detection, but they differ in implementation style, memory characteristics, stack behavior, and even the odd cycles they find when graphs aren't bipartite. This page provides production-ready implementations of both, analyzes their trade-offs, and equips you to choose the right tool for your context.

What You Will Learn

You will implement bipartite detection with both BFS and DFS, understand when to prefer each approach, handle disconnected graphs correctly, learn to extract odd cycles as certificates of non-bipartiteness, and write robust, testable code suitable for production systems.

BFS-Based Bipartite Detection

BFS is often the preferred approach for bipartite detection because its level-by-level traversal naturally corresponds to alternating colors. Vertices at even distances from the start get color 0; vertices at odd distances get color 1.

BFS Approach Summary

Key Idea: Colors alternate by BFS level. Level 0, 2, 4... → Color 0. Level 1, 3, 5... → Color 1.

Data Structures: Queue for BFS frontier, array for colors/visited state.

Time: O(V + E) | Space: O(V)

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
/**
 * Checks if a graph is bipartite using BFS.
 * 
 * @param adjacencyList - Map from vertex to array of neighbors
 * @param n - Number of vertices (0 to n-1)
 * @returns Object containing result and either partition or odd cycle
 */
interface BFSBipartiteResult {
  isBipartite: boolean;
  partition: { colorZero: number[]; colorOne: number[] } | null;
  oddCycleWitness: number[] | null;
}
 
function isBipartiteBFS(
  adjacencyList: Map<number, number[]>,
  n: number
): BFSBipartiteResult {
  // Color array: -1 = unvisited, 0 = first color, 1 = second color
  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 startVertex = 0; startVertex < n; startVertex++) {
    // Skip already visited vertices
    if (color[startVertex] !== -1) continue;
    
    // Initialize BFS from this component's starting vertex
    const queue: number[] = [];
    queue.push(startVertex);
    color[startVertex] = 0;
    
    while (queue.length > 0) {
      const current = queue.shift()!;
      const neighbors = adjacencyList.get(current) || [];
      
      for (const neighbor of neighbors) {
        // Case 1: Self-loop (immediate conflict)
        if (neighbor === current) {
          return {
            isBipartite: false,
            partition: null,
            oddCycleWitness: [current], // Self-loop is odd cycle of length 1
          };
        }
        
        // Case 2: Unvisited neighbor
        if (color[neighbor] === -1) {
          color[neighbor] = 1 - color[current]; // Alternate color
          parent[neighbor] = current;
          queue.push(neighbor);
        }
        // Case 3: Already visited with SAME color (conflict!)
        else if (color[neighbor] === color[current]) {
          // Found odd cycle - reconstruct it
          const oddCycle = reconstructOddCycleBFS(current, neighbor, parent);
          return {
            isBipartite: false,
            partition: null,
            oddCycleWitness: oddCycle,
          };
        }
        // Case 4: Already visited with different color - expected, continue
      }
    }
  }
  
  // No conflicts found - graph is bipartite
  const colorZero: number[] = [];
  const colorOne: number[] = [];
  
  for (let v = 0; v < n; v++) {
    if (color[v] === 0) colorZero.push(v);
    else if (color[v] === 1) colorOne.push(v);
    // Note: isolated vertices get color 0 when we start BFS from them
  }
  
  return {
    isBipartite: true,
    partition: { colorZero, colorOne },
    oddCycleWitness: null,
  };
}
 
/**
 * Reconstructs an odd cycle given two same-colored adjacent vertices.
 * The cycle is: path(u to LCA) + path(LCA to v) + edge(v, u)
 */
function reconstructOddCycleBFS(
  u: number,
  v: number,
  parent: number[]
): number[] {
  // Build path from u to root
  const pathFromU: number[] = [];
  const visitedByU = new Set<number>();
  
  let current = u;
  while (current !== -1) {
    pathFromU.push(current);
    visitedByU.add(current);
    current = parent[current];
  }
  
  // Build path from v until we hit a node visited by u
  const pathFromV: number[] = [];
  current = v;
  while (current !== -1 && !visitedByU.has(current)) {
    pathFromV.push(current);
    current = parent[current];
  }
  
  // 'current' is now the lowest common ancestor (LCA)
  const lca = current;
  
  // Build the cycle: 
  // Start from u, go up to LCA, then go down to v, then edge v-u closes it
  const cycle: number[] = [];
  
  // u up to LCA
  for (const node of pathFromU) {
    cycle.push(node);
    if (node === lca) break;
  }
  
  // LCA down to v (reverse the pathFromV)
  const reversedV = pathFromV.slice().reverse();
  cycle.push(...reversedV);
  
  return cycle;
}

BFS Execution Characteristics:

1. Level-Synchronized Coloring BFS processes vertices level by level. All vertices discovered at the same time (same BFS level) receive the same color. This makes reasoning about correctness very intuitive.

2. Short Odd Cycles Found First When a conflict is detected, BFS tends to find shorter odd cycles because it explores close vertices before distant ones. This can be useful for debugging or providing minimal counterexamples.

3. Memory Pattern The queue can grow to O(V) in the worst case (e.g., a star graph where the center connects to all vertices). For most graphs, queue size stays manageable.

4. Iterative (No Stack Overflow) BFS uses an explicit queue, so it never causes stack overflow regardless of graph size. This is important for production systems with large graphs.

DFS-Based Bipartite Detection

DFS explores as deep as possible before backtracking. For bipartite detection, DFS alternates colors as it descends. The recursive nature makes the code compact, but care is needed to handle large graphs that might overflow the call stack.

DFS Approach Summary

Key Idea: Color alternates with each recursive call. Parent has color X → child gets color (1-X).

Data Structures: Implicit call stack (recursive) or explicit stack (iterative), array for colors.

Time: O(V + E) | Space: O(V) for recursion depth in worst case

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
/**
 * Checks if a graph is bipartite using recursive DFS.
 * 
 * WARNING: May cause stack overflow on very deep graphs (>10K depth).
 * Use iterative version for production with large graphs.
 */
interface DFSBipartiteResult {
  isBipartite: boolean;
  partition: { colorZero: number[]; colorOne: number[] } | null;
  oddCycleWitness: number[] | null;
}
 
function isBipartiteDFSRecursive(
  adjacencyList: Map<number, number[]>,
  n: number
): DFSBipartiteResult {
  const color: number[] = new Array(n).fill(-1);
  const parent: number[] = new Array(n).fill(-1);
  
  // Result object to capture odd cycle if found
  let foundOddCycle: number[] | null = null;
  
  /**
   * DFS helper that returns true if the subgraph rooted here is bipartite.
   */
  function dfs(vertex: number, currentColor: number): boolean {
    color[vertex] = currentColor;
    
    const neighbors = adjacencyList.get(vertex) || [];
    for (const neighbor of neighbors) {
      // Self-loop check
      if (neighbor === vertex) {
        foundOddCycle = [vertex];
        return false;
      }
      
      if (color[neighbor] === -1) {
        // Unvisited: recurse with opposite color
        parent[neighbor] = vertex;
        if (!dfs(neighbor, 1 - currentColor)) {
          return false; // Propagate failure
        }
      } else if (color[neighbor] === currentColor) {
        // Conflict! Same color neighbor
        foundOddCycle = reconstructOddCycleDFS(vertex, neighbor, parent);
        return false;
      }
      // Different color is expected - continue
    }
    
    return true;
  }
  
  // Process each connected component
  for (let start = 0; start < n; start++) {
    if (color[start] !== -1) continue;
    
    if (!dfs(start, 0)) {
      return {
        isBipartite: false,
        partition: null,
        oddCycleWitness: foundOddCycle,
      };
    }
  }
  
  // Collect partitions
  const colorZero: number[] = [];
  const colorOne: number[] = [];
  for (let v = 0; v < n; v++) {
    if (color[v] === 0) colorZero.push(v);
    else if (color[v] === 1) colorOne.push(v);
  }
  
  return {
    isBipartite: true,
    partition: { colorZero, colorOne },
    oddCycleWitness: null,
  };
}
 
function reconstructOddCycleDFS(
  u: number,
  v: number,
  parent: number[]
): number[] {
  // In DFS, u is current vertex, v is the neighbor that caused conflict
  // The odd cycle is: u -> ... -> LCA -> ... -> v -> u
  
  const pathFromU: number[] = [];
  const visitedByU = new Set<number>();
  
  let current = u;
  while (current !== -1) {
    pathFromU.push(current);
    visitedByU.add(current);
    current = parent[current];
  }
  
  const pathFromV: number[] = [];
  current = v;
  while (!visitedByU.has(current)) {
    pathFromV.push(current);
    current = parent[current];
  }
  const lca = current;
  
  const cycle: number[] = [];
  for (const node of pathFromU) {
    cycle.push(node);
    if (node === lca) break;
  }
  cycle.push(...pathFromV.reverse());
  
  return 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
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
/**
 * Iterative DFS bipartite detection - safe for arbitrarily large graphs.
 * Uses explicit stack instead of recursion.
 */
function isBipartiteDFSIterative(
  adjacencyList: Map<number, number[]>,
  n: number
): DFSBipartiteResult {
  const color: number[] = new Array(n).fill(-1);
  const parent: number[] = new Array(n).fill(-1);
  
  for (let start = 0; start < n; start++) {
    if (color[start] !== -1) continue;
    
    // Explicit stack: [vertex, assignedColor]
    const stack: Array<[number, number]> = [[start, 0]];
    
    while (stack.length > 0) {
      const [vertex, assignedColor] = stack.pop()!;
      
      // If already colored, check for conflict
      if (color[vertex] !== -1) {
        if (color[vertex] !== assignedColor) {
          // This shouldn't happen with correct implementation
          // but let's be defensive
          continue;
        }
        continue; // Already processed with correct color
      }
      
      // Assign color
      color[vertex] = assignedColor;
      
      const neighbors = adjacencyList.get(vertex) || [];
      for (const neighbor of neighbors) {
        // Self-loop
        if (neighbor === vertex) {
          return {
            isBipartite: false,
            partition: null,
            oddCycleWitness: [vertex],
          };
        }
        
        if (color[neighbor] === -1) {
          // Unvisited: push with opposite color
          parent[neighbor] = vertex;
          stack.push([neighbor, 1 - assignedColor]);
        } else if (color[neighbor] === assignedColor) {
          // Conflict! Same color
          const oddCycle = reconstructOddCycleDFS(vertex, neighbor, parent);
          return {
            isBipartite: false,
            partition: null,
            oddCycleWitness: oddCycle,
          };
        }
      }
    }
  }
  
  // Build partitions
  const colorZero: number[] = [];
  const colorOne: number[] = [];
  for (let v = 0; v < n; v++) {
    if (color[v] === 0) colorZero.push(v);
    else if (color[v] === 1) colorOne.push(v);
  }
  
  return {
    isBipartite: true,
    partition: { colorZero, colorOne },
    oddCycleWitness: null,
  };
}

Recursion Depth Limits

In languages like JavaScript/TypeScript, default stack limits are often around 10,000-15,000 calls. A path graph with 100,000 vertices would overflow the stack with recursive DFS. Always use iterative DFS for production systems handling graphs of unknown size.

BFS vs. DFS — Detailed Comparison

Both BFS and DFS achieve the same goal with identical time complexity, but their characteristics differ in important ways. Understanding these differences helps you choose the right approach for your specific context.

BFS vs. DFS for Bipartite Detection
Aspect	BFS	DFS
Time Complexity	O(V + E)	O(V + E)
Space Complexity	O(V) for queue	O(V) for stack/recursion
Implementation	Always iterative (queue)	Naturally recursive; iterative possible
Code Complexity	Slightly more verbose	Elegant recursive form
Stack Safety	✅ Always safe	⚠️ Recursive can overflow
Traversal Order	Level by level	Depth first, then backtrack
Odd Cycles Found	Tends to find shorter cycles	May find longer cycles
Memory Locality	Poor (queue spans levels)	Better (stack is local)
Parallelization	Easier (level-parallel)	Harder (deep dependencies)
Debugging	Easier to trace levels	Harder to follow deep paths

When to Choose BFS:

Production systems with large graphs — BFS is always iterative, eliminating stack overflow risk.
When you need the shortest odd cycle — BFS discovers shorter cycles first.
When debugging/visualizing — Level-by-level progression is easier to understand.
When parallelism matters — Levels can be processed in parallel.

When to Choose DFS:

Quick prototypes — Recursive DFS is very compact to write.
When graph diameter is small — No stack overflow concern.
When memory locality matters — DFS has better cache behavior.
When you need to track other DFS properties — Like discovery/finish times for topological sort.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Graph (tree structure for clarity):
              0
           /  |  \
          1   2   3
         /|   |   |\
        4 5   6   7 8
 
BFS traversal order: 0, 1, 2, 3, 4, 5, 6, 7, 8
  Level 0: [0]
  Level 1: [1, 2, 3]
  Level 2: [4, 5, 6, 7, 8]
  → Colors: 0, 1, 1, 1, 0, 0, 0, 0, 0
 
DFS traversal order (one possibility): 0, 1, 4, 5, 2, 6, 3, 7, 8
  Goes deep into 0→1→4, backtracks, then 0→1→5, backtracks, then 0→2→6, ...
  → Colors: 0, 1, 0, 0, 1, 0, 1, 0, 0
 
Both produce valid 2-colorings!
The partition {0, 4, 5, 6, 7, 8} vs {1, 2, 3} works either way.

Practical Recommendation

For most production use cases, iterative BFS is the safest choice. It's stack-safe, easy to debug, and integrates well with standard graph processing patterns. Use recursive DFS only when you're certain about depth limits or when integrating with other DFS-based algorithms.

Handling Disconnected Graphs

A commonly overlooked aspect of bipartite detection is handling disconnected graphs — graphs with multiple connected components. A single BFS/DFS from one starting vertex only explores that component. If other components exist, they remain unvisited.

Key Insight: Component Independence

A disconnected graph is bipartite if and only if every connected component is bipartite. If any single component contains an odd cycle, the entire graph is non-bipartite.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Component 1 (Bipartite):      Component 2 (NOT Bipartite):
    
    0 ────── 1                      4
    │        │                     / \
    │        │                    5───6
    3 ────── 2                    
 
Component 1: Square (4-cycle) → Bipartite ✓
  Partition: {0, 2}, {1, 3}
 
Component 2: Triangle (3-cycle) → NOT Bipartite ✗
  No valid 2-coloring exists
 
Overall graph: NOT Bipartite
  Because component 2 fails the 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
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
/**
 * Processes all components correctly.
 * The outer loop ensures we don't miss any component.
 */
function isBipartiteAllComponents(
  adjacencyList: Map<number, number[]>,
  n: number
): {
  isBipartite: boolean;
  components: Array<{
    vertices: number[];
    partition: { colorZero: number[]; colorOne: number[] } | null;
  }>;
  failedComponent?: {
    vertices: number[];
    oddCycle: number[];
  };
} {
  const color: number[] = new Array(n).fill(-1);
  const parent: number[] = new Array(n).fill(-1);
  const componentId: number[] = new Array(n).fill(-1);
  
  const components: Array<{
    vertices: number[];
    partition: { colorZero: number[]; colorOne: number[] } | null;
  }> = [];
  
  let currentComponentId = 0;
  
  for (let start = 0; start < n; start++) {
    if (color[start] !== -1) continue; // Already in a processed component
    
    // BFS for this component
    const queue: number[] = [start];
    color[start] = 0;
    componentId[start] = currentComponentId;
    
    const componentVertices: number[] = [];
    let componentBipartite = true;
    let oddCycle: number[] | null = null;
    
    while (queue.length > 0) {
      const u = queue.shift()!;
      componentVertices.push(u);
      
      for (const v of adjacencyList.get(u) || []) {
        if (v === u) {
          // Self-loop
          componentBipartite = false;
          oddCycle = [u];
          continue;
        }
        
        if (color[v] === -1) {
          color[v] = 1 - color[u];
          parent[v] = u;
          componentId[v] = currentComponentId;
          queue.push(v);
        } else if (color[v] === color[u] && componentBipartite) {
          componentBipartite = false;
          oddCycle = reconstructOddCycleBFS(u, v, parent);
        }
      }
    }
    
    if (componentBipartite) {
      const colorZero = componentVertices.filter(v => color[v] === 0);
      const colorOne = componentVertices.filter(v => color[v] === 1);
      components.push({
        vertices: componentVertices,
        partition: { colorZero, colorOne },
      });
    } else {
      // Return immediately on first failed component
      return {
        isBipartite: false,
        components,
        failedComponent: {
          vertices: componentVertices,
          oddCycle: oddCycle || [],
        },
      };
    }
    
    currentComponentId++;
  }
  
  return {
    isBipartite: true,
    components,
  };
}
 
// Helper function (same as before)
function reconstructOddCycleBFS(u: number, v: number, parent: number[]): number[] {
  const pathFromU: number[] = [];
  const visitedByU = new Set<number>();
  let current = u;
  while (current !== -1) {
    pathFromU.push(current);
    visitedByU.add(current);
    current = parent[current];
  }
  const pathFromV: number[] = [];
  current = v;
  while (!visitedByU.has(current)) {
    pathFromV.push(current);
    current = parent[current];
  }
  const lca = current;
  const cycle: number[] = [];
  for (const node of pathFromU) {
    cycle.push(node);
    if (node === lca) break;
  }
  cycle.push(...pathFromV.reverse());
  return cycle;
}

Component Processing Strategy:

Approach 1: Early Exit (Default) Stop as soon as any component fails. This is efficient when you only care about the yes/no answer.

Approach 2: Full Analysis Process all components even after finding a failed one. Useful when you want to identify all problematic components or analyze the full graph structure.

Approach 3: Lazy Processing Use a generator/iterator pattern to process components on-demand. Useful for very large graphs where you want to yield control between components.

Common Bug: Forgetting the Outer Loop

A frequent mistake is running BFS/DFS from only vertex 0 without the outer loop. This works if the graph is connected, but silently gives wrong answers for disconnected graphs. Always iterate through all vertices to catch unvisited components.

Odd Cycle Extraction — Certificates of Non-Bipartiteness

When a graph is not bipartite, it's valuable to provide a certificate — concrete evidence of why the test failed. For bipartiteness, this certificate is an odd cycle. Extracting this cycle isn't just academically interesting; it has practical applications in debugging, validation, and explaining results to users.

Why Extract Odd Cycles?

Verification: A third party can verify your 'not bipartite' answer by checking the cycle has odd length and all edges exist.

Debugging: When a graph should be bipartite but isn't, the cycle shows exactly what went wrong.

User Feedback: In applications like scheduling, the cycle explains why a conflict exists.

How Odd Cycle Extraction Works:

When BFS/DFS finds a conflict (edge connecting two same-colored vertices u and v), we have:

Edge (u, v) — The conflict edge
Path u → root — Via parent pointers
Path v → root — Via parent pointers

The odd cycle is formed by:

Path from u up to the lowest common ancestor (LCA)
Path from LCA down to v
Edge from v back to u

The total length is odd because:

Distance(root, u) ≡ color[u] (mod 2)
Distance(root, v) ≡ color[v] (mod 2)
Since color[u] == color[v], distances have same parity
Cycle length = (dist_u - dist_lca) + (dist_v - dist_lca) + 1
= (dist_u + dist_v) - 2*dist_lca + 1
Since dist_u and dist_v have same parity, their sum is even
Even - even + 1 = odd ✓

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
/**
 * Extracts an odd cycle and validates it.
 */
interface OddCycleResult {
  cycle: number[];          // Vertices in cycle order
  cycleEdges: [number, number][];  // Edges forming the cycle
  length: number;           // Cycle length (should be odd)
  isValid: boolean;         // Validation result
}
 
function extractAndValidateOddCycle(
  adjacencyList: Map<number, number[]>,
  u: number,
  v: number,
  parent: number[]
): OddCycleResult {
  // Extract the cycle
  const pathU: number[] = [];
  const visitedByU = new Map<number, number>(); // vertex -> position in pathU
  
  let curr = u;
  let pos = 0;
  while (curr !== -1) {
    pathU.push(curr);
    visitedByU.set(curr, pos);
    curr = parent[curr];
    pos++;
  }
  
  const pathV: number[] = [];
  curr = v;
  while (curr !== -1 && !visitedByU.has(curr)) {
    pathV.push(curr);
    curr = parent[curr];
  }
  const lca = curr!;
  const lcaPos = visitedByU.get(lca)!;
  
  // Build cycle vertices
  const cycle: number[] = [];
  for (let i = 0; i <= lcaPos; i++) {
    cycle.push(pathU[i]);
  }
  for (let i = pathV.length - 1; i >= 0; i--) {
    cycle.push(pathV[i]);
  }
  
  // Build cycle edges
  const cycleEdges: [number, number][] = [];
  for (let i = 0; i < cycle.length; i++) {
    const from = cycle[i];
    const to = cycle[(i + 1) % cycle.length];
    cycleEdges.push([from, to]);
  }
  
  // Validate the cycle
  const isValidCycle = validateOddCycle(adjacencyList, cycle, cycleEdges);
  
  return {
    cycle,
    cycleEdges,
    length: cycle.length,
    isValid: isValidCycle,
  };
}
 
/**
 * Validates that:
 * 1. The cycle has odd length
 * 2. All edges in the cycle exist in the graph
 * 3. Vertices form a proper cycle (first == last conceptually)
 */
function validateOddCycle(
  adjacencyList: Map<number, number[]>,
  cycle: number[],
  cycleEdges: [number, number][]
): boolean {
  // Check odd length
  if (cycle.length % 2 === 0) {
    console.error(`Validation failed: cycle length ${cycle.length} is even`);
    return false;
  }
  
  // Check all edges exist
  for (const [from, to] of cycleEdges) {
    const neighbors = adjacencyList.get(from) || [];
    if (!neighbors.includes(to)) {
      console.error(`Validation failed: edge (${from}, ${to}) not in graph`);
      return false;
    }
  }
  
  // Check cycle is closed
  const lastEdge = cycleEdges[cycleEdges.length - 1];
  if (lastEdge[1] !== cycle[0]) {
    console.error(`Validation failed: cycle not closed`);
    return false;
  }
  
  return true;
}
 
// Example usage:
function demonstrateOddCycleExtraction() {
  // Triangle graph: 0-1-2-0
  const graph = new Map<number, number[]>([
    [0, [1, 2]],
    [1, [0, 2]],
    [2, [0, 1]],
  ]);
  
  // Simulate finding conflict at edge (1, 2) after coloring 0→0, 1→1, 2→1
  const parent = [-1, 0, 0]; // parent[1]=0, parent[2]=0
  
  const result = extractAndValidateOddCycle(graph, 1, 2, parent);
  console.log("Odd cycle:", result.cycle);
  console.log("Length:", result.length);
  console.log("Valid:", result.isValid);
  // Output: [1, 0, 2], Length: 3, Valid: true
}

Minimal Odd Cycles

The extracted cycle isn't necessarily the shortest odd cycle in the graph, but it's a valid witness. For finding the actual shortest odd cycle, more sophisticated algorithms are needed (e.g., BFS from each vertex taking O(VE) total time).

Testing Your Implementation

Robust bipartite detection requires thorough testing. Beyond basic correctness, we need to verify edge cases, stress test with large inputs, and validate extracted odd cycles.

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
// Test utilities
function createGraph(n: number, edges: [number, number][]): Map<number, number[]> {
  const graph = new Map<number, number[]>();
  for (let i = 0; i < n; i++) graph.set(i, []);
  for (const [u, v] of edges) {
    graph.get(u)!.push(v);
    graph.get(v)!.push(u); // Undirected
  }
  return graph;
}
 
function runTests() {
  // =========================================
  // TEST CATEGORY 1: Bipartite Graphs
  // =========================================
  
  // Test 1.1: Empty graph
  const empty = createGraph(0, []);
  assert(isBipartiteBFS(empty, 0).isBipartite === true, "Empty graph should be bipartite");
  
  // Test 1.2: Single vertex, no edges
  const single = createGraph(1, []);
  assert(isBipartiteBFS(single, 1).isBipartite === true, "Single vertex bipartite");
  
  // Test 1.3: Two vertices, one edge
  const pair = createGraph(2, [[0, 1]]);
  assert(isBipartiteBFS(pair, 2).isBipartite === true, "Simple edge bipartite");
  
  // Test 1.4: Path graph (always bipartite)
  const path = createGraph(5, [[0,1], [1,2], [2,3], [3,4]]);
  assert(isBipartiteBFS(path, 5).isBipartite === true, "Path graph bipartite");
  
  // Test 1.5: Even cycle (square)
  const square = createGraph(4, [[0,1], [1,2], [2,3], [3,0]]);
  assert(isBipartiteBFS(square, 4).isBipartite === true, "Square bipartite");
  
  // Test 1.6: Even cycle (hexagon)
  const hexagon = createGraph(6, [[0,1],[1,2],[2,3],[3,4],[4,5],[5,0]]);
  assert(isBipartiteBFS(hexagon, 6).isBipartite === true, "Hexagon bipartite");
  
  // Test 1.7: Complete bipartite K_{3,3}
  const k33 = createGraph(6, [
    [0,3],[0,4],[0,5], [1,3],[1,4],[1,5], [2,3],[2,4],[2,5]
  ]);
  assert(isBipartiteBFS(k33, 6).isBipartite === true, "K_{3,3} bipartite");
  
  // Test 1.8: Tree (always bipartite)
  const tree = createGraph(7, [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]]);
  assert(isBipartiteBFS(tree, 7).isBipartite === true, "Tree bipartite");
  
  // =========================================
  // TEST CATEGORY 2: Non-Bipartite Graphs
  // =========================================
  
  // Test 2.1: Triangle
  const triangle = createGraph(3, [[0,1], [1,2], [2,0]]);
  const triResult = isBipartiteBFS(triangle, 3);
  assert(triResult.isBipartite === false, "Triangle not bipartite");
  assert(triResult.oddCycleWitness!.length === 3, "Triangle cycle length 3");
  
  // Test 2.2: Pentagon (5-cycle)
  const pentagon = createGraph(5, [[0,1],[1,2],[2,3],[3,4],[4,0]]);
  const pentResult = isBipartiteBFS(pentagon, 5);
  assert(pentResult.isBipartite === false, "Pentagon not bipartite");
  assert(pentResult.oddCycleWitness!.length % 2 === 1, "Pentagon cycle odd");
  
  // Test 2.3: Self-loop
  const selfLoop = new Map([[0, [0, 1]], [1, [0]]]);
  const slResult = isBipartiteBFS(selfLoop, 2);
  assert(slResult.isBipartite === false, "Self-loop not bipartite");
  
  // Test 2.4: K_4 (complete graph on 4 vertices)
  const k4 = createGraph(4, [[0,1],[0,2],[0,3],[1,2],[1,3],[2,3]]);
  assert(isBipartiteBFS(k4, 4).isBipartite === false, "K_4 not bipartite");
  
  // =========================================
  // TEST CATEGORY 3: Disconnected Graphs
  // =========================================
  
  // Test 3.1: Two bipartite components
  const twoBipartite = createGraph(4, [[0,1], [2,3]]);
  assert(isBipartiteBFS(twoBipartite, 4).isBipartite === true, "Two edges bipartite");
  
  // Test 3.2: One bipartite, one not
  const mixedGraph = new Map<number, number[]>([
    [0, [1]], [1, [0]],  // Component 1: bipartite
    [2, [3, 4]], [3, [2, 4]], [4, [2, 3]]  // Component 2: triangle
  ]);
  assert(isBipartiteBFS(mixedGraph, 5).isBipartite === false, "Mixed should fail");
  
  // =========================================
  // TEST CATEGORY 4: Partition Validation
  // =========================================
  
  // Test 4.1: Check partition validity
  const g = createGraph(4, [[0,1], [1,2], [2,3], [3,0]]);
  const result = isBipartiteBFS(g, 4);
  assert(result.isBipartite, "Square bipartite");
  const {colorZero, colorOne} = result.partition!;
  // Every edge should cross partition
  for (const [u, v] of [[0,1], [1,2], [2,3], [3,0]]) {
    const uInZero = colorZero.includes(u);
    const vInZero = colorZero.includes(v);
    assert(uInZero !== vInZero, "Edge must cross partition");
  }
  
  console.log("All tests passed!");
}
 
function assert(condition: boolean, message: string) {
  if (!condition) throw new Error(`Assertion failed: ${message}`);
}

Testing Checklist

•Basic cases: Empty, single vertex, single edge, path, tree
•Even cycles: Square (C_4), hexagon (C_6), octagon (C_8)
•Odd cycles: Triangle (C_3), pentagon (C_5), heptagon (C_7)
•Complete bipartite: K_{2,2}, K_{2,3}, K_{3,3}, K_{5,5}
•Complete graphs: K_3, K_4, K_5 (all non-bipartite for n ≥ 3)
•Disconnected: Multiple bipartite components, mixed components
•Edge cases: Self-loops, parallel edges, isolated vertices
•Large inputs: 10K, 100K, 1M vertices for performance testing
•Partition validation: Verify every edge crosses the partition
•Odd cycle validation: Verify extracted cycles are valid and odd

Summary: BFS/DFS-Based Detection

We've covered the complete implementation landscape for bipartite detection. Let's consolidate the key insights:

Key Takeaways

•Both BFS and DFS work — They have identical time complexity O(V + E) and produce correct results.
•BFS is safer for production — Always iterative, no stack overflow risk, level-based coloring is intuitive.
•DFS is elegant for prototyping — Compact recursive form, but use iterative version for large graphs.
•Don't forget disconnected graphs — The outer loop over all vertices is essential for correctness.
•Odd cycle extraction is valuable — Provides certificates/witnesses for non-bipartiteness.
•Thorough testing is crucial — Cover edge cases, validate partitions, verify odd cycles.

What's Next:

With detection algorithms mastered, the final page explores the rich world of applications. Bipartite graphs aren't just a theoretical curiosity — they power matching algorithms, scheduling systems, and optimization problems that arise constantly in real-world software systems.

Implementation Complete

You now have production-ready implementations of bipartite detection using both BFS and DFS. You understand their trade-offs, can handle edge cases correctly, and can extract odd cycles as certificates. This knowledge directly translates to interview success and real-world system design.