Find all of the distinct non-planar graphs with 6 vertices. Find all of the distinct non-planar graphs with 6 vertices.  Draw a picture of each such graph, and explain why the graphs you have found are the only possibilities.
HINT: Proceed by cases, considering the number of edges in each possible graph.
 A: Hint In any planar graph with 6 vertices you have 
$$e \leq 3v-6=12 .$$
This proves that any graph with at least 13 edges is non-planar.
All you need to do now, is check the graphs with 12 or less edges.
Since $K_5$ has $10$ edges and $K_{3,3}$ has $9$ edges, any non-planar graph has at least 9 edges.
9 edges: Your graph must be $K_{3,3,}$ (Why?)
10 edges: Your graph must be $K_{3,3,}$ with an extra edge or $K_5$ with an isolated vertex. (Why?)
11 edges and 12 edges: If your graph contains $K_{3,3}$, it is easy: it must be $K_{3,3}$ with enough extra edges. 
For $K_5$ you need to look at two different situations: your graph contains $K_5$ as a subgraph, or the sixth vertex is the vertex of degree $2$ in a subdivision of $K_5$. 
A: By Kuratowski's Theorem you are looking for the graph that have either the subdivisions of the $K_{3,3}$ or the $K_5$ as a subgraph.
The $K_{3,3}$ is a nonplanar graph with 6 vertices. For the other graphs, start with a $K_5$ and add a vertex. You have now different possibilities how to connect (or not connect) the additional vertex to the $K_5$. Try to go through all the cases by iterating over the degree of the additional vertex. Finally, you have the $K_5$ with a subdivided edge.
