Graph Coloring and Hamiltonian Path: Backtracking on Graphs

Problem Statement#

Two graph problems live under the same backtracking umbrella:

• M-Coloring (classic): given an undirected graph with n vertices and m colors, decide whether the vertices can be colored so that no two adjacent vertices share a color. Returns true/false plus an example coloring.
• Hamiltonian Path/Cycle: given an undirected graph, find a path (or cycle) that visits every vertex exactly once.

Both problems are NP-complete in general but small enough to brute force with backtracking when n is up to roughly 20. They are foundational for understanding constraint satisfaction and search-tree pruning.

A simpler 2-color variant — Bipartite Check (LeetCode 785) — runs in polynomial time via BFS/DFS coloring and is a common interview softball.

Why This Problem Matters#

Graph coloring and Hamiltonian path are textbook backtracking problems used at Amazon, Google, and Microsoft to test whether candidates can adapt the recursion-with-state-restoration template to graph constraints. The bipartite check (LeetCode 785) is a common medium that exercises the same idea in 2-color form. Candidates who can write the m-coloring code clean and discuss why the problem is NP-hard in general signal serious algorithmic depth.

These problems are also gateways to constraint-satisfaction frameworks (Sudoku is essentially graph coloring), scheduling (rooms = colors, classes = vertices), and register allocation in compilers.

The Core Insight (decision tree / state space)#

For m-coloring: state is a partially colored vertex array colors[0..v-1]. Decision at each vertex v: try colors 1 through m, skip a color if any neighbor already uses it. If no color works, backtrack.

For Hamiltonian path: state is the current path and the visited set. Decision at the path's last vertex: try each unvisited neighbor; if recursion succeeds, return; else backtrack.

The branching factor is m for coloring (typically small) and up to n - 1 for Hamiltonian path. The depth is n in both cases. The is_safe (or constraint check) function is what makes pruning effective: most color choices fail immediately at most vertices.

A good ordering heuristic for m-coloring is to process the highest-degree vertex first (it has the most constraints, so it forces decisions earliest).

Visual Dry Run (recursion tree)#

For a 4-vertex cycle graph with m = 3:

color v0 with 1
  color v1: not 1 -> try 2
    color v2: not 2 -> try 1 (v2 not adjacent to v0)
                       Wait: v2 is adjacent to v1 only in cycle, so 1 is fine
      color v3: not 1 (adj v0) and not 1 (adj v2)
                also not adj v1 -> try 3
                v3=3 works -> SUCCESS

Each level branches up to m ways, but constraint pruning kills most branches.

For a triangle graph with m = 2:

color v0 = 1
  color v1: not 1 -> 2
    color v2: not 1 (adj v0) and not 2 (adj v1) -> no color works -> backtrack
  no other choice for v1 -> backtrack
color v0 = 2
  ... symmetric failure
return false

The triangle requires 3 colors (chromatic number 3), so 2-coloring fails as expected.

Solution (Optimal) — Python + JavaScript with backtracking template, complexity#

M-Coloring:

def m_coloring(graph, m):
    n = len(graph)
    colors = [0] * n
 
    def is_safe(v, c):
        for u in range(n):
            if graph[v][u] and colors[u] == c:
                return False
        return True
 
    def backtrack(v):
        if v == n:
            return True
        for c in range(1, m + 1):
            if is_safe(v, c):
                colors[v] = c
                if backtrack(v + 1):
                    return True
                colors[v] = 0
        return False
 
    return (True, colors) if backtrack(0) else (False, [])

Hamiltonian Cycle:

def hamiltonian_cycle(graph):
    n = len(graph)
    path = [0]
    visited = [False] * n
    visited[0] = True
 
    def backtrack():
        if len(path) == n:
            return graph[path[-1]][0] == 1
        last = path[-1]
        for v in range(1, n):
            if not visited[v] and graph[last][v]:
                visited[v] = True
                path.append(v)
                if backtrack():
                    return True
                path.pop()
                visited[v] = False
        return False
 
    return path + [0] if backtrack() else []

function mColoring(graph, m) {
  const n = graph.length;
  const colors = new Array(n).fill(0);
  const isSafe = (v, c) => {
    for (let u = 0; u < n; u++) {
      if (graph[v][u] && colors[u] === c) return false;
    }
    return true;
  };
  const backtrack = (v) => {
    if (v === n) return true;
    for (let c = 1; c <= m; c++) {
      if (isSafe(v, c)) {
        colors[v] = c;
        if (backtrack(v + 1)) return true;
        colors[v] = 0;
      }
    }
    return false;
  };
  return backtrack(0) ? colors : null;
}
 
function hamiltonianCycle(graph) {
  const n = graph.length;
  const path = [0];
  const visited = new Array(n).fill(false);
  visited[0] = true;
  const backtrack = () => {
    if (path.length === n) return graph[path[path.length - 1]][0] === 1;
    const last = path[path.length - 1];
    for (let v = 1; v < n; v++) {
      if (!visited[v] && graph[last][v]) {
        visited[v] = true;
        path.push(v);
        if (backtrack()) return true;
        path.pop();
        visited[v] = false;
      }
    }
    return false;
  };
  return backtrack() ? [...path, 0] : [];
}

Complexity: m-coloring is O(m^n) worst case. Hamiltonian path is O(n!) worst case. Both are NP-hard in general; pruning brings practical runtimes down dramatically for sparse graphs.

For bipartite check (2-coloring), BFS or DFS in O(V + E) is sufficient — no backtracking needed because the coloring is forced once the first vertex is colored.

Common Mistakes#

• Forgetting to undo the assignment on backtrack — leaves stale colors in the array.
• Confusing path.append(v) and visited[v] = True order. They must be paired and undone together.
• Off-by-one in Hamiltonian cycle — forgetting to check the edge back to the start.
• Using m-coloring with m = 2 when bipartite BFS is asymptotically faster.
• Not exploiting graph structure (vertex degree ordering) — leads to slow backtracking on dense graphs.

Interview Tips#

• Distinguish the easy 2-coloring case (BFS, polynomial) from the general m-coloring case (NP-hard, backtracking).
• Mention vertex ordering: "I will process the highest-degree vertex first to fail fast." This is constraint-propagation gold.
• For Hamiltonian, note the connection to Traveling Salesman.
• Reference LeetCode 785 (Is Graph Bipartite?) and LeetCode 886 (Possible Bipartition) as practical interview problems.

Follow-up Questions#

• LeetCode 785 (Is Graph Bipartite?): polynomial-time 2-coloring via BFS/DFS.
• LeetCode 886 (Possible Bipartition): bipartite check on a "dislike" graph.
• Chromatic number: smallest m for which the graph is m-colorable. Binary search on m.
• Traveling Salesman: Hamiltonian cycle weighted by edge cost; bitmask DP gives O(n^2 times 2^n).

Key Takeaways#

• Graph coloring and Hamiltonian path are NP-hard backtracking classics.
• The template is identical: assign-recurse-undo with a constraint check.
• M-coloring is O(m^n); Hamiltonian path is O(n!); both prune dramatically in sparse graphs.
• Bipartite check (2-coloring) is polynomial via BFS/DFS — special case worth recognizing.
• Vertex ordering by degree turbocharges m-coloring in practice.
• These problems are gateways to constraint-satisfaction frameworks, scheduling, and register allocation.

Sources:

• M-Coloring Problem - GeeksforGeeks
• Hamiltonian Cycle - GeeksforGeeks