Which of the non-planar graphs below have the property that the removal of any vertex and all edges incidents to it produces a planar graph?

Question

(a) K5

(b) K6

(c) K3,3

(d) K3,4

I do not understand how I can resolve these issues.

Answer 1

Let's go case by case:

a) When you remove any node from a $K_N$ graph, you get a $K_{N-1}$ graph. Hence, we know that $K_4$ is planar, and hence, a) is True

b) Using our reasoning from a), regardless of what node we remove, the remaining graph will be $K_5$, which is not planar, hence b) is False

c) Regardless of what node we remove, the remaining graph will be of the form $K_{3,2}$ or $K_{2,3}$, both of which are planar, hence c) is True

d) If we remove a node from $K_{3,4}$ such that the remaining graph is $K_{3,3}$, then the remaining graph is not planar, so d) is False.