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.

-
I am guessing that this is homework. What have you tried? – Kris Williams May 20 '13 at 0:27

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

-

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.

-