M-Coloring Problem
Description
You are given an undirected graph with V vertices (numbered 0 to V−1) and a list of edges, along with an integer m representing the number of available colors.
Your task is to determine whether it is possible to assign one of the m colors to every vertex such that no two adjacent vertices share the same color. Two vertices are adjacent if there is an edge directly connecting them.
This is known as the graph coloring problem — a classic constraint-satisfaction problem. If a valid coloring exists using at most m colors, return true. Otherwise, return false.
Key observations:
- Vertices that are NOT connected by an edge are allowed to have the same color.
- The problem asks whether ANY valid coloring exists, not to find all possible colorings.
- The order in which you assign colors does not matter — only the final assignment must be valid.
Examples
Example 1
Input: V = 4, edges = [[0,1], [1,3], [2,3], [3,0], [0,2]], m = 3
Output: true
Explanation: One valid coloring is:
- Vertex 0 → Color 1
- Vertex 1 → Color 2
- Vertex 2 → Color 2
- Vertex 3 → Color 3
Let us verify: Edge (0,1): colors 1 ≠ 2 ✓. Edge (1,3): colors 2 ≠ 3 ✓. Edge (2,3): colors 2 ≠ 3 ✓. Edge (3,0): colors 3 ≠ 1 ✓. Edge (0,2): colors 1 ≠ 2 ✓. No adjacent pair shares a color. Note that vertices 1 and 2 both have color 2, but they are not adjacent, so this is allowed.
Example 2
Input: V = 3, edges = [[0,1], [1,2], [0,2]], m = 2
Output: false
Explanation: Vertices 0, 1, and 2 form a triangle — every pair is connected. With only 2 colors, at least two adjacent vertices must share a color. Suppose vertex 0 gets color 1, vertex 1 must get color 2 (adjacent to 0). Then vertex 2 is adjacent to both: it cannot be color 1 (same as vertex 0) or color 2 (same as vertex 1). No color is available. The graph is NOT 2-colorable.
Example 3
Input: V = 3, edges = [[0,1], [1,2], [0,2]], m = 3
Output: true
Explanation: The same triangle graph, but now with 3 colors. Assign vertex 0 → color 1, vertex 1 → color 2, vertex 2 → color 3. Each vertex has a unique color, so no two adjacent vertices share one. A complete graph on k vertices always needs exactly k colors.
Constraints
- 1 ≤ V ≤ 10
- 1 ≤ E ≤ V × (V − 1) / 2
- 0 ≤ edges[i][j] ≤ V − 1
- 1 ≤ m ≤ V
- The graph has no self-loops or duplicate edges
Editorial
Brute Force
Intuition
The most straightforward way to solve this problem is to enumerate every possible way to color the graph and check whether any of them is valid.
Imagine you have V vertices and m paint buckets. For each vertex, you independently choose one of the m colors. This gives m × m × ... × m = m^V total color configurations. For each configuration, you scan all edges to check whether any edge connects two vertices of the same color. If you find even one valid configuration, return true. If none of the m^V configurations works, return false.
This approach is like trying every possible combination on a lock — you are guaranteed to find the answer, but you waste enormous effort checking configurations that are obviously wrong. For instance, if vertex 0 and vertex 1 are adjacent and both get color 1, there is no reason to keep generating the remaining V−2 vertex colors. But the brute force does exactly that — it generates the full configuration first and validates only at the end.
Step-by-Step Explanation
Let us trace through Example 1: V = 4, edges = [[0,1],[1,3],[2,3],[3,0],[0,2]], m = 3.
The brute force generates all 3^4 = 81 color configurations and validates each one.
Step 1: Generate configuration color = [1, 1, 1, 1] (all vertices get color 1).
- Check edge (0,1): color[0]=1, color[1]=1 → SAME! Invalid.
- This configuration fails immediately.
Step 2: Generate configuration color = [1, 1, 1, 2].
- Check edge (0,1): color[0]=1, color[1]=1 → SAME! Invalid.
- Still fails because vertices 0 and 1 are always both color 1.
Step 3: Generate configuration color = [1, 1, 1, 3].
- Check edge (0,1): 1 == 1 → Invalid. Same problem.
Step 4: Through step 9, all configurations starting with [1, 1, ...] fail because vertices 0 and 1 are adjacent and both assigned color 1.
Step 5: Generate configuration color = [1, 2, 1, 1].
- Edge (0,1): 1 ≠ 2 ✓. Edge (1,3): 2 ≠ 1 ✓. Edge (2,3): 1 == 1 → Invalid!
- Vertices 2 and 3 are adjacent with the same color.
Step 6: Generate configuration color = [1, 2, 1, 2].
- Edge (0,1): 1 ≠ 2 ✓. Edge (1,3): 2 == 2 → Invalid! Vertices 1 and 3 share color 2.
Step 7: Generate configuration color = [1, 2, 1, 3].
- Edge (0,1): 1 ≠ 2 ✓. Edge (1,3): 2 ≠ 3 ✓. Edge (2,3): 1 ≠ 3 ✓. Edge (3,0): 3 ≠ 1 ✓. Edge (0,2): 1 == 1 → Invalid!
- Vertices 0 and 2 are adjacent with the same color.
Step 8: Eventually, we reach configuration color = [1, 2, 2, 3].
- Edge (0,1): 1 ≠ 2 ✓. Edge (1,3): 2 ≠ 3 ✓. Edge (2,3): 2 ≠ 3 ✓. Edge (3,0): 3 ≠ 1 ✓. Edge (0,2): 1 ≠ 2 ✓.
- All edges valid! Return true.
Observation: We checked many configurations before finding a valid one. For 9 of the first 10 tries, the failure was detectable at vertex 0 or 1, but the brute force still generated the remaining vertices needlessly.
Algorithm
- Build an adjacency list from the edge list.
- Create a color array of size V, initialized to 0 (uncolored).
- Recursively generate all color configurations:
- For vertex
i, try each color from 1 to m. - After assigning a color, recurse to the next vertex.
- When all V vertices are assigned (base case), validate the entire configuration.
- For vertex
- To validate: iterate over all edges. If any edge connects two vertices with the same color, the configuration is invalid.
- If any valid configuration is found, return true. If all m^V configurations are invalid, return false.
Code
#include <vector>
using namespace std;
class Solution {
public:
bool isValid(vector<int> adj[], vector<int>& color, int v) {
for (int i = 0; i < v; i++) {
for (int neighbor : adj[i]) {
if (color[i] == color[neighbor])
return false;
}
}
return true;
}
bool generate(int vertex, vector<int>& color, int m,
vector<int> adj[], int v) {
if (vertex == v) {
return isValid(adj, color, v);
}
for (int c = 1; c <= m; c++) {
color[vertex] = c;
if (generate(vertex + 1, color, m, adj, v))
return true;
color[vertex] = 0;
}
return false;
}
bool graphColoring(int v, vector<vector<int>>& edges, int m) {
vector<int> adj[v];
for (auto& e : edges) {
adj[e[0]].push_back(e[1]);
adj[e[1]].push_back(e[0]);
}
vector<int> color(v, 0);
return generate(0, color, m, adj, v);
}
};class Solution:
def graphColoring(self, v, edges, m):
adj = [[] for _ in range(v)]
for u, w in edges:
adj[u].append(w)
adj[w].append(u)
color = [0] * v
def is_valid():
for i in range(v):
for neighbor in adj[i]:
if color[i] == color[neighbor]:
return False
return True
def generate(vertex):
if vertex == v:
return is_valid()
for c in range(1, m + 1):
color[vertex] = c
if generate(vertex + 1):
return True
color[vertex] = 0
return False
return generate(0)import java.util.*;
class Solution {
private boolean isValid(List<List<Integer>> adj,
int[] color, int v) {
for (int i = 0; i < v; i++) {
for (int neighbor : adj.get(i)) {
if (color[i] == color[neighbor])
return false;
}
}
return true;
}
private boolean generate(int vertex, int[] color, int m,
List<List<Integer>> adj, int v) {
if (vertex == v) {
return isValid(adj, color, v);
}
for (int c = 1; c <= m; c++) {
color[vertex] = c;
if (generate(vertex + 1, color, m, adj, v))
return true;
color[vertex] = 0;
}
return false;
}
public boolean graphColoring(int v, int[][] edges, int m) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < v; i++)
adj.add(new ArrayList<>());
for (int[] e : edges) {
adj.get(e[0]).add(e[1]);
adj.get(e[1]).add(e[0]);
}
int[] color = new int[v];
return generate(0, color, m, adj, v);
}
}Complexity Analysis
Time Complexity: O((V + E) × m^V)
There are m^V total color configurations to generate. For each complete configuration, validating it requires scanning all edges, which takes O(V + E) using an adjacency list. In the worst case, we check all configurations before finding a valid one (or concluding none exists), giving O((V + E) × m^V).
For V = 10 and m = 10, this is 10^10 configurations times edge checking — far too slow even for the small constraints.
Space Complexity: O(V + E)
The adjacency list takes O(V + E) space. The color array uses O(V). The recursion stack is at most V frames deep, so O(V). Total: O(V + E).
Why This Approach Is Not Efficient
The brute force generates all m^V color combinations before checking validity. This is wasteful because it ignores constraint violations until the very end.
The core problem: If vertex 0 and vertex 1 are adjacent and both get color 1, there is ZERO chance any extension of this configuration can be valid. Yet the brute force still generates all m^(V−2) ways to color the remaining vertices before discovering the conflict. For V = 10, m = 10, that means generating 10^8 useless configurations after a single bad pair.
What we need is early pruning. Instead of generating a complete configuration and then checking, we should check constraints as we go. Before assigning a color to vertex i, verify that none of its already-colored neighbors has the same color. If a color conflicts, skip it immediately and try the next color. If NO color works for vertex i, backtrack to vertex i−1 and try a different color there.
This is the essence of backtracking: check constraints at each step and prune invalid branches immediately, rather than exploring them fully.
Optimal Approach - Backtracking with Constraint Checking
Intuition
Imagine you are painting houses on a street where certain pairs of houses must have different colors. Instead of painting all houses first and then walking the street to check for violations, you paint one house at a time. Before picking up a paint bucket for the current house, you look at all the already-painted neighboring houses. If a color would create a conflict, you skip it. If no color works at all, you go back to the previous house and try a different color for it.
This is the backtracking approach. We process vertices one by one (0, 1, 2, ... V−1). For each vertex, we try each color from 1 to m. Before committing to a color, we run a safety check: scan all neighbors of the current vertex that have already been colored. If any neighbor has the same color, it is unsafe. Only when the color passes the safety check do we assign it and move to the next vertex.
If we exhaust all m colors for a vertex and none is safe, we backtrack — undo the color assignment of the previous vertex and try the next color for it. This cascading undo can go back several vertices if needed.
The key advantage over brute force: we never generate an assignment that is known to be invalid. Every partial assignment in the recursion tree satisfies the coloring constraint for all edges involving already-colored vertices. This prunes the search space dramatically.
Step-by-Step Explanation
Let us trace Example 1: V = 4, edges = [[0,1],[1,3],[2,3],[3,0],[0,2]], m = 3.
Adjacency list: 0→{1,3,2}, 1→{0,3}, 2→{3,0}, 3→{1,0,2}.
Step 1: Start with color = [0, 0, 0, 0] (0 means uncolored). Begin with vertex 0.
Step 2: Vertex 0 — try color 1. No neighbors are colored yet, so the safety check passes trivially. Assign color[0] = 1. Move to vertex 1.
- color = [1, 0, 0, 0]
Step 3: Vertex 1 — try color 1. Check neighbor 0: color[0] = 1, same as 1 → CONFLICT! Color 1 is not safe.
Step 4: Vertex 1 — try color 2. Check neighbor 0: color[0] = 1 ≠ 2 → safe. Neighbor 3: uncolored → safe. Assign color[1] = 2. Move to vertex 2.
- color = [1, 2, 0, 0]
Step 5: Vertex 2 — try color 1. Check neighbor 3: uncolored → ok. Check neighbor 0: color[0] = 1, same as 1 → CONFLICT! Color 1 is not safe.
Step 6: Vertex 2 — try color 2. Check neighbor 3: uncolored → ok. Check neighbor 0: color[0] = 1 ≠ 2 → safe. Assign color[2] = 2. Move to vertex 3.
- color = [1, 2, 2, 0]
Step 7: Vertex 3 — try color 1. Check neighbor 1: color[1] = 2 ≠ 1 → ok. Check neighbor 0: color[0] = 1, same as 1 → CONFLICT!
Step 8: Vertex 3 — try color 2. Check neighbor 1: color[1] = 2, same as 2 → CONFLICT!
Step 9: Vertex 3 — try color 3. Check neighbor 1: color[1] = 2 ≠ 3 → ok. Check neighbor 0: color[0] = 1 ≠ 3 → ok. Check neighbor 2: color[2] = 2 ≠ 3 → ok. All safe! Assign color[3] = 3.
- color = [1, 2, 2, 3]
Step 10: All V = 4 vertices are colored. Return true.
Result: The graph IS 3-colorable. Assignment: {0→1, 1→2, 2→2, 3→3}. We only explored 6 color assignments (steps 2-4 and 5-9) instead of all 81 brute-force combinations.
Backtracking — Coloring Vertices One by One — Watch how we assign colors to vertices sequentially, check safety against neighbors, skip conflicting colors, and only commit when safe.
Algorithm
- Build an adjacency list from the edge list.
- Create a color array of size V, initialized to 0 (uncolored).
- Call the recursive function solve(vertex):
- Base case: If vertex == V, all vertices are colored → return true.
- Recursive case: For each color c from 1 to m:
- Run
isSafe(vertex, c): check if any neighbor ofvertexalready has color c. - If safe:
- Assign color[vertex] = c.
- Recurse to solve(vertex + 1).
- If recursion returns true, propagate true upward.
- Otherwise, undo: color[vertex] = 0 (backtrack).
- If no color is safe, return false (triggers backtracking in the caller).
- Run
- Return the result of solve(0).
Code
#include <vector>
using namespace std;
class Solution {
public:
bool isSafe(int vertex, int col,
vector<int> adj[], vector<int>& color) {
for (int neighbor : adj[vertex]) {
if (color[neighbor] == col)
return false;
}
return true;
}
bool solve(int vertex, int m,
vector<int> adj[], vector<int>& color, int v) {
if (vertex == v)
return true;
for (int c = 1; c <= m; c++) {
if (isSafe(vertex, c, adj, color)) {
color[vertex] = c;
if (solve(vertex + 1, m, adj, color, v))
return true;
color[vertex] = 0;
}
}
return false;
}
bool graphColoring(int v, vector<vector<int>>& edges, int m) {
vector<int> adj[v];
for (auto& e : edges) {
adj[e[0]].push_back(e[1]);
adj[e[1]].push_back(e[0]);
}
vector<int> color(v, 0);
return solve(0, m, adj, color, v);
}
};class Solution:
def graphColoring(self, v, edges, m):
adj = [[] for _ in range(v)]
for u, w in edges:
adj[u].append(w)
adj[w].append(u)
color = [0] * v
def is_safe(vertex, c):
for neighbor in adj[vertex]:
if color[neighbor] == c:
return False
return True
def solve(vertex):
if vertex == v:
return True
for c in range(1, m + 1):
if is_safe(vertex, c):
color[vertex] = c
if solve(vertex + 1):
return True
color[vertex] = 0
return False
return solve(0)import java.util.*;
class Solution {
private boolean isSafe(int vertex, int col,
List<List<Integer>> adj, int[] color) {
for (int neighbor : adj.get(vertex)) {
if (color[neighbor] == col)
return false;
}
return true;
}
private boolean solve(int vertex, int m,
List<List<Integer>> adj, int[] color, int v) {
if (vertex == v)
return true;
for (int c = 1; c <= m; c++) {
if (isSafe(vertex, c, adj, color)) {
color[vertex] = c;
if (solve(vertex + 1, m, adj, color, v))
return true;
color[vertex] = 0;
}
}
return false;
}
public boolean graphColoring(int v, int[][] edges, int m) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < v; i++)
adj.add(new ArrayList<>());
for (int[] e : edges) {
adj.get(e[0]).add(e[1]);
adj.get(e[1]).add(e[0]);
}
int[] color = new int[v];
return solve(0, m, adj, color, v);
}
}Complexity Analysis
Time Complexity: O(V × m^V)
In the worst case, the backtracking algorithm still tries all m^V possible colorings. For each attempted coloring of a vertex, the isSafe function scans up to V−1 neighbors, costing O(V) per call. This gives O(V × m^V) worst-case time.
However, in practice, the backtracking prunes the search tree dramatically. For most real-world graphs, the actual running time is far below the worst case because conflicts are detected early, preventing exploration of entire subtrees. The earlier a conflict is detected, the more work is saved.
Space Complexity: O(V + E)
The adjacency list uses O(V + E) space. The color array uses O(V). The recursion stack is at most V frames deep (one per vertex), adding O(V). The isSafe function uses O(1) extra space per call. Total: O(V + E).
Comparison with Brute Force:
- Brute force validates after generating the FULL configuration → O((V+E) × m^V)
- Backtracking validates at EACH vertex → O(V × m^V) worst case, but far fewer configurations explored in practice
- Both use O(V + E) space, but backtracking is practically much faster due to early pruning