You are given an undirected graph with V vertices (labeled 0 to V-1) and E edges, described by a list edges where each entry [u, v] is an undirected edge between vertices u and v. You are also given an integer m, the number of available colors.
Decide whether you can assign a color to every vertex — using at most m colors — so that no edge connects two vertices of the same color. Return true if such a coloring exists, and false otherwise.
You do not have to use all m colors; m is only an upper bound. The graph uses 0-based vertex labels.
Input: V = 4, edges = [[0,1],[1,3],[2,3],[3,0],[0,2]], m = 3 Output: true One valid coloring with 3 colors: 0->1, 1->2, 2->2, 3->3. Every edge joins two different colors.
Input: V = 3, edges = [[0,1],[1,2],[0,2]], m = 2 Output: false Vertices 0, 1, 2 form a triangle where all three are mutually adjacent, so they need 3 distinct colors — 2 is not enough.
- 1 <= V <= 10 - 1 <= E <= V*(V-1)/2 - 0 <= edges[i][0], edges[i][1] <= V-1 - 1 <= m <= V
Graph coloring is the classic backtracking problem: hand out colors so that no two neighbors match, using no more than m of them. We'll go from a paint-everything brute force to a prune-early backtracking search.
v, then recursing on v+1.Formally: find an assignment color[v] in {1..m} for every vertex such that for every edge (u, v), color[u] != color[v]. Return whether one exists.
Worked example — V = 4, m = 3, edges: 0-1, 1-3, 2-3, 3-0, 0-2
0
/|\
1 | 2
\|/
3
one valid coloring (colors 1..3):
0 -> 1 1 -> 2 2 -> 2 3 -> 3
check each edge:
0-1: 1!=2 1-3: 2!=3 2-3: 2!=3 3-0: 3!=1 0-2: 1!=2
all endpoints differ -> answer: true
Asking before you code shows you probe the input contract instead of assuming it — a senior habit.
“Is the graph simple, with no self-loops or duplicate edges?”
A self-loop makes a vertex adjacent to itself, so it could never be colored — confirming this rules out a trivial false answer.
“Must I use exactly m colors, or at most m?”
At most — using fewer is allowed, so the real bar is m being at least the graph's chromatic number.
“How large can V get?”
With V at most 10, an exponential backtracking search fits the time limit easily; a much larger V would force heuristics.
Before I code, a few quick clarifications.
Is the graph simple — no self-loops or parallel edges?
And m is an upper bound, so using fewer colors is fine?
Since V is at most 10, backtracking will comfortably fit the time limit.
When you color vertex v, the only constraints that matter are neighbors that already have a color. Uncolored neighbors impose nothing yet — so you only need to scan those.
The brute force paints all V vertices and validates last. But a clash is permanent — once two neighbors match, no future choice can repair it. So test each color before committing and prune whole subtrees of doomed paintings.
brute: color all V, then check -> explores dead branches fully smart: check, then color -> kills a bad branch immediately
If a vertex has no safe color, the fault lies in an earlier choice. Undo the previous vertex's color and try its next option. That single 'undo and retry' is the backtracking that makes the search tractable.
| Brute force | Optimal | |
|---|---|---|
| Time | O(m^V · E) | O(V · m^V) worst case, pruned |
| Space | O(V + E) | O(V + E) |
| Idea | color all, check last | check first, backtrack on failure |
The full code for both lives in the Approaches selector below.
Key takeaway
Graph coloring is constraint satisfaction by backtracking: assign the next variable only a value that's locally consistent, recurse, and undo the moment you're stuck. The same 'choose → check → recurse → undo' skeleton solves N-Queens and Sudoku too.
solve(v):
if v == V: return true
for c in 1..m:
if no neighbor of v already has color c:
color[v] = c
if solve(v + 1): return true
color[v] = 0 # undo, backtrack
return false