Welcome to our community

Be a part of something great, join today!

[SOLVED] Statement of a theorem due to Bondy.

caffeinemachine

Well-known member
MHB Math Scholar
Mar 10, 2012
834
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?
 

Bacterius

Well-known member
MHB Math Helper
Jan 26, 2012
644
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

Well-known member
MHB Math Scholar
Mar 10, 2012
834
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.
 

Bacterius

Well-known member
MHB Math Helper
Jan 26, 2012
644

caffeinemachine

Well-known member
MHB Math Scholar
Mar 10, 2012
834
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. :)