this question might be simple to others, but I'm stuck on this question. "prove that when I deleted an edge from $K5$, it has planar sub-graph .
So, I know that G is planar if and only if G contains no sub-division of $K5$ or $K3,3$. So that means when I delete an edge from K5, I no loger have sub-division of K5 and therefore, the subgraph is planar. But how do I show that explicitly that when I remove edge from $K5$, it will have planar subgraph? (I think this question is somewhat related to Kuratowski's theorem)
Best Answer
The key observation is that all graphs of "$K_5$ with one edge removed" are isomorphic.
To this end, you can just start with a picture of $K_5$, remove any one edge, and then try to re-draw what results as a planar graph. The important component is understanding why this approach generalizes enough to prove the graph is planar for any single edge-removal.
To this end, here is a picture that came up after googling K5 graph planar:
By way of a similar argument, you can reason about $K_{3,3}$ and draw a convincing picture:
(From wikipedia here.)
Without loss of generality, the removed edge could be one of the two that cross above.