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.

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$. 
