Graph Theory Question

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

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

Graph Theory Question

Postby Ddanndt » Thu Oct 20, 2016 11:58 am UTC

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

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

Re: Graph Theory Question

Postby Flumble » Thu Oct 20, 2016 12:46 pm UTC

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?

Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 31 guests