How do you prove a graph **is not** planar? 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. 

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.
