Decide Whether an Undirected Graph Can Be Colored with Three Colors

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

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

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

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

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.