Color each vertex so that no two adjacent vertices share the same color. This page shows the backtracking logic: try color → check conflict → go deeper → undo and try next.
Backtracking topic from DAA handout: Graph Coloring
Mental model: Check → Choose → Recurse → Undo
Interactive Graph
uncolored current vertex conflict / reject accepted / solution backtracked
Current vertex
-
Trying color
-
Step type
Ready
Result
Waiting to start
Tip: watch what happens after a valid color is placed. The algorithm still comes back later to try another sibling choice if needed. That return step is the actual backtrack.
Try Yourself
Pick a color, then click a graph node. The graph will immediately tell you whether that move is valid.
Selected color:Color 1
Color all vertices so that adjacent nodes differ.
Backtracking Logic
Preferred textbook pattern
1
solve(vertex):
2
if vertex == V:
3
record solution
4
return
5
for color = 1 to m:
6
if not isSafe(vertex, color): continue
7
assign color to vertex
8
solve(vertex + 1)
9
remove color // backtrack
This panel explains the current step in plain language.
Traversal Log
How to read this
State = which vertex we are coloring now. Choice = which color we try on that vertex. Constraint = no adjacent vertex can have the same color. Undo = remove the color when returning from recursion.