## Graph Theory Question

**Moderators:** gmalivuk, Moderators General, Prelates

### Graph Theory Question

Suppose that a graph is a maximal planar graph. Is it true that ,except for a finite number of exceptions, the complements of the maximal planar graphs have traceable connected components. Traceable = having a hamiltonian path. I've only a few counterexamples with a small number of vertices e.g 7. Are there any large maximal planar graph whose complement doesn't have a traceable connected component?

God does not care about our mathematical difficulties — He integrates empirically.

—Albert Einstein

—Albert Einstein

### Re: Graph Theory Question

Is this perhaps homework? It doesn't sound like homework —because who in their right mind would ask such a thing as homework?— but then again I don't know what satanic rituals people perform in mathematics studies.

Have you tried proving that for a sufficiently large graph Ore's theorem holds? Or that a non-Hamiltonian complement requires a K3,3 or other non-planar subgraph in the original graph?

Or the other way: proving that you can add vertices to your counterexamples while keeping them counterexamples?

Have you tried proving that for a sufficiently large graph Ore's theorem holds? Or that a non-Hamiltonian complement requires a K3,3 or other non-planar subgraph in the original graph?

Or the other way: proving that you can add vertices to your counterexamples while keeping them counterexamples?

### Who is online

Users browsing this forum: No registered users and 9 guests