Is the Graph Three-Colourable?
An undirected graph has n vertices, 0 to n - 1, and edges. Return whether the vertices can be coloured with three colours so that no edge joins two vertices of the same colour.
isThreeColorable(3, [[0, 1], [1, 2], [2, 0]]) -> true isThreeColorable(4, [[0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3]]) -> false // K4
Hints
Hint 1
Assign colours vertex by vertex. For vertex i, try each of the three colours that no already-coloured neighbour has; recurse; undo and try the next colour when the recursion fails.
Hint 2
Fix the first vertex's colour to 0 — the three colourings that differ only by renaming are the same, and skipping them cuts the search by a factor of three.