Statement of a theorem due to Bondy.

  • Context: MHB 
  • Thread starter Thread starter caffeinemachine
  • Start date Start date
  • Tags Tags
    Theorem
Click For Summary

Discussion Overview

The discussion revolves around the conditions of a theorem related to Hamiltonian graphs and pancyclic graphs, specifically a strengthened form of Mantel's theorem. Participants explore the implications of edge counts in non-bipartite graphs and the requirements for Hamiltonian cycles, examining potential misunderstandings regarding the theorem's applicability.

Discussion Character

  • Technical explanation
  • Debate/contested

Main Points Raised

  • One participant cites a source stating that a non-bipartite graph with at least $n^2/4$ edges must have a Hamiltonian cycle, but presents a counterexample with a graph that does not meet this condition.
  • Another participant clarifies that the theorem applies specifically to Hamiltonian graphs and suggests that the conditions may have been misinterpreted.
  • A later reply confirms the correct statement of the theorem found in a different source, indicating that the original reference lacked the necessary clause regarding Hamiltonian properties.
  • Participants express uncertainty about whether the theorem applies only to connected graphs.

Areas of Agreement / Disagreement

Participants do not reach a consensus on the applicability of the theorem to non-bipartite graphs, with multiple interpretations of the conditions presented. Some participants agree on the need for clarification regarding Hamiltonian properties, while others remain uncertain about the implications of the theorem.

Contextual Notes

There are limitations regarding the assumptions made about the conditions of the theorem and whether it applies to disconnected graphs. The discussion highlights potential misunderstandings in the interpretation of the theorem's requirements.

caffeinemachine
Gold Member
MHB
Messages
799
Reaction score
15
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?
 
Physics news on Phys.org
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.
 
Bacterius said:
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 said:
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. :)
 

Similar threads

MHB Proving Turan's Theorem (Dual Version) and its Implications for $ex(n, K_{p+1})$
  • · Replies 1 ·
Replies
1
Views
2K
MHB Is HSC NP-Complete in Graph Theory?
  • · Replies 1 ·
Replies
1
Views
2K
MHB Some basic questions on Graph theory
  • · Replies 2 ·
Replies
2
Views
2K
MHB Understanding the Theorem for Feasible Solutions of Difference Constraints
  • · Replies 15 ·
Replies
15
Views
3K
MHB Graph Theory. Decomposition of K_{2n+1} into hamiltonian cycles.
  • · Replies 2 ·
Replies
2
Views
5K
MHB Another tree-related graph theory proof
  • · Replies 1 ·
Replies
1
Views
2K
MHB Graph theory proof related to trees
  • · Replies 1 ·
Replies
1
Views
2K
Graduate Does G with all its degrees at least three contain a cycle with a chord?
  • · Replies 3 ·
Replies
3
Views
4K
Undergrad Understanding Theorem 13 from Calculus 7th ed, R. Adams, C. Essex, 4.10
  • · Replies 10 ·
Replies
10
Views
3K
How to construct a graph with girth = twice the diameter + 1
  • · Replies 2 ·
Replies
2
Views
2K