TITLE: determining whether $H$ is a nonplanar graph
QUESTION [1 upvotes]: Determine, with justification, whether the graph $H$ below is nonplanar.


I think it's nonplanar as I can find a $K_{3,3}$ subdivision for it. I can describe the subdivision as follows. Join vertex $8$ to vertex $9$ (as they are connected by the path $812349$). Then add an edge from vertex $4$ to vertex $9$ (as they are connected by the path $439$). Add an edge from $4$ to $7$ as they're connected by the path $4397$. Now delete the edges $18, 12, 23, 34, 14, 39, 37, 79,29$ (since we added edges $49$ and $89$, there are $9$ edges remaining). Delete the vertices of the resulting graph with degree zero, which are $1, 2,3.$ The result is the $K_{3,3}$ graph with vertices $5,7,9$ on one side of the graph and vertices $8,6,4$ on the other, which shows that $H$ has a $K_{3,3}$ subdivision, and hence is nonplanar.

I think my reasoning may be incorrect as I obtained the subdivision incorrectly. If so, is there a way to obtain a correct $K_{3,3}$ subdivision? I know the $5$ vertices of degree $4$ are all joined by a path to each other, so that might be useful.

REPLY [0 votes]: If you contract edges $81$, $12$, $65$, $43$, you will get $K_5$.
{"set_name": "stack_exchange", "score": 1, "question_id": 3894055}