Decide Whether an Undirected Graph Can Be Colored with Three Colors
Company: Snowflake
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given an undirected graph, decide whether every node can be given one of three colors so that no edge connects two nodes of the same color.
### Function Signature
```python
def can_three_color(n: int, edges: list[list[int]]) -> bool:
```
### Rules
- The graph has `n` nodes numbered `0` to `n - 1`, and each pair `[a, b]` in `edges` is an undirected edge between nodes `a` and `b`.
- Return `True` if each node can be assigned one of three colors so that the two endpoints of every edge have different colors, and `False` otherwise. Not every color has to be used.
### Constraints
- `1 <= n <= 15`
- `0 <= len(edges) <= n * (n - 1) / 2`
- For every edge, `a != b` and both are between `0` and `n - 1`; no edge is listed twice, in either direction.
- The graph does not have to be connected.
### Examples
**Example 1**
```text
Input: n = 4, edges = [[0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3]]
Output: False
```
Every pair of the four nodes is connected, so all four need different colors.
**Example 2**
```text
Input: n = 5, edges = [[0, 1], [1, 2], [2, 3], [3, 4], [4, 0]]
Output: True
```
Two colors are not enough for a cycle of odd length, but three are: for example, colors 0, 1, 0, 1, 2 around the cycle.
**Example 3**
```text
Input: n = 6, edges = [[0, 1], [1, 2], [2, 3], [3, 4], [4, 0], [5, 0], [5, 1], [5, 2], [5, 3], [5, 4]]
Output: False
```
Node 5 touches all of nodes 0 to 4, so those five would have to share the two remaining colors, which is impossible around a cycle of odd length. No four nodes are all connected to one another, yet three colors still do not suffice.
Overview: Given an undirected graph with up to fifteen nodes, decide whether every node can receive one of three colors so that no edge joins two nodes of the same color. It tests backtracking search with pruning and reasoning about odd cycles and cliques.
Given an undirected graph, decide whether every node can be given one of three colors so that no edge connects two nodes of the same color.
Implement `can_three_color(n, edges)`:
- The graph has `n` nodes numbered `0` to `n - 1`, and each pair `[a, b]` in `edges` is an undirected edge between nodes `a` and `b`, so `[a, b]` and `[b, a]` describe the same edge.
- Return `True` if each node can be assigned one of three colors so that the two endpoints of every edge have different colors, and `False` otherwise (`true` / `false` in JavaScript, Java and C++). Not every color has to be used.
- Only this yes/no answer is returned, not a coloring.
### Constraints
- `1 <= n <= 15`
- `0 <= len(edges) <= n * (n - 1) / 2`
- For every edge, `a != b` and both are between `0` and `n - 1`; no edge is listed twice, in either direction.
- The graph does not have to be connected.
- Every value fits in a 32-bit signed integer; nothing can exceed 2^31 - 1.
### Example 1
```text
Input: n = 5, edges = [[0, 1], [1, 2], [2, 3], [3, 4], [4, 0]]
Output: True
```
Two colors are not enough for a cycle of odd length, but three are: for example, colors 0, 1, 0, 1, 2 around the cycle.
### Example 2
```text
Input: n = 6, edges = [[0, 1], [1, 2], [2, 3], [3, 4], [4, 0], [5, 0], [5, 1], [5, 2], [5, 3], [5, 4]]
Output: False
```
Node 5 touches all of nodes 0 to 4, so those five would have to share the two remaining colors, which is impossible around a cycle of odd length. No four nodes are all connected to one another, yet three colors still do not suffice.
Constraints
- 1 <= n <= 15
- 0 <= len(edges) <= n * (n - 1) / 2
- For every edge, a != b and both are between 0 and n - 1; no edge is listed twice, in either direction.
- The graph does not have to be connected.
- Every value fits in a 32-bit signed integer; nothing can exceed 2^31 - 1.
Examples
Input: (1, [])
Expected Output: True
Explanation: Minimum valid input: one node and no edges, so a single color suffices.
Input: (15, [])
Expected Output: True
Explanation: n at its upper bound 15 with no edges: every node can share one color, and unused colors are allowed.
Hints
- Each edge is listed once but constrains both of its endpoints, and parts of the graph that share no edge never constrain each other.
- Ruling out four mutually connected nodes is not enough: in the second example, a node adjacent to every node of an odd cycle already makes three colors impossible.
- The three colors are interchangeable and not every color must be used, so two colorings that differ only by renaming the colors count as the same answer.