## Graph Theory Question

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

Ddanndt
Posts: 60
Joined: Fri Oct 02, 2009 4:18 pm UTC
Location: Paris

### 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

Flumble
Yes Man
Posts: 2227
Joined: Sun Aug 05, 2012 9:35 pm UTC

### 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?