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: