agilot / satapps Goto Github PK

Description

The four colors theorem states that any (loopless) planar graph admits a four-coloring. In order to add a nice test case to our VertexColoring solver we can implement an algorithm that checks whether a graph is planar and then verify in our test cases whether these graphs can be 4-colored.

Tasks

• Write a function that checks whether a graph is planar (implementable in $\mathcal{O}(|E|)$)
• Write a test case that generates random graphs and checks that they admit a 4-coloring when they are planar