Original question: $G$ is a simple undirected planar graph with 9 vertices. Suppose that every vertex in G has the same degree (regular). Prove or disprove that the complementary graph $\bar G$ must have a Hamiltonian cycle.
This is part of a past paper for a discrete math course, but the answers were not provided. I have tried to do it for a while now, but I don't even have any idea how to start this proof. Could someone please point me in the right direction, or even better, show me how to do this?