MHB Statement of a theorem due to Bondy.

[caffeinemachine]

On this page Turán's theorem - Wikipedia, the free encyclopediaI found that:

"A strengthened form of Mantel's theorem states that any graph with at least $n^2/4$ edges must either be a complete bipartite graph $K_{n/2,n/2}$ or it must be pancyclic, i.e, not only does it contain a triangle, it must also contain cycles of all other possible lengths up to the number of vertices."

Now a special case of this is:

A non-bipartite graph $G$ with $|E(G)|\geq n^2/4$, where $n=|V(G)|$, has a Hamiltonian Cycle.

But if we consider the $10$ vertex graph $G$ which has a $9$-clique and an isolated vertex then we see that $|E(G)|=36>10^2/4$ but $G$ doesn't have a Hamiltonian cycle.

What has gone wrong here? What am I missing?

 

[Nono713]

What I read is:

A strengthened form of Mantel's theorem states that any hamiltonian graph with at least n2/4 edges must either be the complete bipartite graph Kn/2,n/2 or it must be pancyclic: not only does it contain a triangle, it must also contain cycles of all other possible lengths up to the number of vertices in the graph (Bondy 1971).

So the special case is really:

A non-bipartite hamiltonian graph G satisfies $|E(G)| \geq n^2 / 4$ where $n = |V(G)|$.

Which does not imply that a non-bipartite graph satisfying this condition is hamiltonian.

So maybe you got the conditions the other way around. I could be wrong though.. it's late. If not, maybe the theorem only applies to connected graphs.

 

[caffeinemachine]

What I read is:
So the special case is really:
Which does not imply that a non-bipartite graph satisfying this condition is hamiltonian.

So maybe you got the conditions the other way around. I could be wrong though.. it's late. If not, maybe the theorem only applies to connected graphs.

You are right Bacterius. I found the correct statement on ScienceDirect.com - Journal of Combinatorial Theory, Series B - Pancyclic graphs I and had corrected it on wiki. Wiki didn't have tjhe clause 'Hamiltonian' there.

 

[Nono713]

You are right Bacterius. I found the correct statement on ScienceDirect.com - Journal of Combinatorial Theory, Series B - Pancyclic graphs I and had corrected it on wiki. Wiki didn't have tjhe clause 'Hamiltonian' there.

Ah, that explains it. Thanks :)

 

[caffeinemachine]

Ah, that explains it. Thanks :)

I almost got bald pulling my hair over this one. BUt finally science direct helped. Phewf. Thanks for taking a look at my problem. :)