Showing that a graph is planar

graph theoryplanar-graphs

G is a graph with 5 vertices with degrees 3,4,5,6,7 (one each), n vertices with degree 2, and m vertices with degree 1.

Prove that G is planar.

I know that to prove G is planar, according to Kuratowski's and Wagner's theorems, I need to show it does not contain any minor of $K_5$ or $K_{3,3}$. But am unsure how to go about it.
For $K_5$, If I'm not wrong, I could use the fact there are only 4 vertices for which $deg_G(v)\geq4$, So it cannot contain a minor of $K_5$.
About $K_{3,3}$, maybe I could show that G contains an odd circle, therefore is not bipartite and does not contain any minor of a bipartite graph. But I do not know how to show it contains an odd circle.

I would appreciate any clarifications about this question! Thank you!

EDIT: Is it true that for G to include a minor of $K_{3,3}$ it needs to have at least 6 vertices with degree at least 3 each? If so, then it sorts that out for me. Thank you.

Best Answer

A graph satisfying the given degree conditions may be planarly embedded as follows:

  1. Unsubdivide to remove degree-$2$ vertices
  2. Remove degree-$1$ vertices
  3. Find a planar embedding of the remaining graph, which now contains only those vertices which originally had degrees $3,4,5,6,7$. This is always possible: because of the originally degree-$3$ vertex this "core" (minus loops and with multiple edges identified) will now always be a subgraph of $K_5-e$, which is planar
  4. Reverse step 2 (add back degree-$1$ vertices; this preserves planarity)
  5. Reverse step 1 (subdivide edges to restore degree-$2$ vertices; this preserves planarity)
Related Question