How do you prove a graph **is not** planar?

Question

Is there a theorem using the number of edges and vertices, or something about the max degree a vertex can have? I know that you can use $e ≤ 3v−6$. But what if that condition holds, and it still might not be planar? I'm having a hard time finding a planar representation for the graph I'm looking at.

Answer 1

As stated above, a variation of Kuratowski's and Wagner's Theorems are popular for proving non-planarity of a graph. Another method could be to simply refer to Euler's Formula for planar graphs i.e. $$v - e + f = 2,$$ Where $v$ is the number of vertices, $e$ is the number of edges, and $f$ is the number of faces. Any connected planar graph has this equality holding, and often we can prove a graph is non-planar by assuming it is planar, and showing that it contradicts the above formula. Another variation of this formula for planar graphs with multiple connected components is $$v - e + f = k + 1,$$ where $k$ is the number of connected components within the graph.