Showing that a graph is planar

Question

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.

Answer 1

The traditional $K_{3,3}$-or-$K_5$ argument also works.

It is easier to use Kuratowski's theorem than Wagner's, because we can immediately say that

• a subdivision of $K_5$ must contain $5$ vertices of degree $4$, and
• a subdivision of $K_{3,3}$ must contain $6$ vertices of degree $3$.

However, our graph only has $5$ vertices of degree $\ge 3$ and only $4$ vertices of degree $\ge 4$, so it cannot contain either subdivision.

For minors, the reasoning would be trickier: it is not true that if a graph $H$ has a vertex of degree $d$, then that vertex must be represented by a degree-$d$ vertex in any $H$-minor. In particular, for any graph $H$ (including $K_5$) there is an $H$-minor with maximum degree $3$. The Petersen graph is a $K_5$-minor. It might still be possible to apply Wagner's theorem, by reasoning about how many vertices of each degree such graphs would need, but it's not worth it.

Answer 2

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)