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 G¯ must have a Hamiltonian cycle.

sublimnes9

sublimnes9

Open question

2022-08-16

G is a simple undirected, regular, and planar graph with 9 vertices. Prove or disprove that G ¯ must have a Hamiltonian cycle.
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 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?

Answer & Explanation

Rose Holmes

Rose Holmes

Beginner2022-08-17Added 9 answers

Planar graph on n vertices has at most 3n−6 edges if n 3 (this follows from Euler's formula). Since G is regular graph on 9 vertices we have deg G 2 21 9 = 4 Then deg G ¯ 4. If deg G ¯ 5 then it is Hamiltonian by Dirac's theorem. The remaning case is deg G ¯ = 4
Futher my solution becomes rather sophisticated in spite of OEIS tells that are at most 16 possible graphs G ¯ left to consider. So I just point that all of them are Hamiltonian.

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?