Katkat
Back

Determine Whether an Undirected Graph Is 3-Colorable

SnowflakeSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests knowledge of graph theory, specifically constraint satisfaction, and the ability to implement a backtracking algorithm to solve NP-complete problems on small constraints.

Problem Statement

Given an undirected graph represented by n vertices (labeled 0 to n-1) and a list of edges, determine if the graph can be colored with at most 3 colors such that no two adjacent vertices share the same color. A graph is 3-colorable if you can assign one of three colors (e.g., 1, 2, 3) to each vertex such that for every edge (u, v), the color of u is not equal to the color of v.

The graph may be disconnected and contain isolated vertices.

Function Signature

def is_three_colorable(n: int, edges: list[tuple[int, int]]) -> bool:

Constraints

  • n <= 20
  • edges can contain any number of connections between vertices.
  • Time limit: 2 seconds.

Examples

Example 1: Input: n = 3, edges = [(0, 1), (1, 2), (2, 0)] Output: True Explanation: This is a triangle; colors {1, 2, 3} satisfy the condition.

Example 2: Input: n = 4, edges = [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)] Output: False Explanation: This is a complete graph K4 (a tetrahedron), which requires 4 colors.

Edge Cases

  • n = 0 or n = 1 (always true).
  • Disconnected components (must ensure all components are valid).
  • Empty edge list (always true).

Hints

Hint 1

Since the number of vertices is very small (n <= 20), consider a recursive backtracking approach to try assigning colors to vertices one by one.

Hint 2

For each uncolored vertex, attempt to assign one of the three available colors, then recursively move to the next vertex if the assignment is valid.

Hint 3

Handle disconnected components by iterating through all vertices and triggering the recursive function for any vertex that has not yet been assigned a color.

Follow-up questions

  • How does the complexity change if we increase n to 100? Is backtracking still viable?
  • Can you optimize the state space by pre-processing the graph to find connected components or using degree-based heuristics?
  • What is the time complexity of your solution in terms of n and the number of edges?