Statement of a theorem due to Bondy.

  • MHB
  • Thread starter caffeinemachine
  • Start date
  • Tags
    Theorem
In summary: I almost got bald pulling my hair over this one. BUt finally science direct helped. Phewf. Thanks for taking a look at my problem.
  • #1
caffeinemachine
Gold Member
MHB
816
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
  • #2
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.
 
  • #3
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.
 
  • #5
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. :)
 

Related to Statement of a theorem due to Bondy.

1. What is the statement of the theorem due to Bondy?

The theorem due to Bondy is a graph theory theorem that states that in any graph with n vertices and m edges, there exists a path from any vertex to any other vertex of length at most n/2. This is also known as the "longest path problem."

2. Who is Bondy and what is their contribution to the theorem?

András Frank Bondy is a Hungarian mathematician who, along with his colleague Robin Wilson, first published the theorem in 1976 in the Journal of Combinatorial Theory. Their contribution was proving the theorem and introducing it to the field of graph theory.

3. How is the Bondy theorem used in graph theory?

The Bondy theorem is used to determine the maximum length of a path in a graph. It is also used in various algorithms and proofs in graph theory, such as in the proof of the Erdős–Gallai theorem.

4. Are there any limitations or exceptions to the Bondy theorem?

Yes, there are a few limitations to the Bondy theorem. The theorem only applies to undirected graphs, and there are some cases where the longest path may not be unique. Additionally, the theorem does not give an algorithm for finding the longest path, it only guarantees its existence.

5. What are some real-world applications of the Bondy theorem?

The Bondy theorem has applications in network routing, transportation planning, and circuit design. It can also be used in computer science for optimizing algorithms that involve finding the longest path in a graph. Additionally, the theorem has implications in the study of complex networks, such as social networks and biological networks.

Similar threads

MHB Proving Turan's Theorem (Dual Version) and its Implications for $ex(n, K_{p+1})$
    • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
MHB Is HSC NP-Complete in Graph Theory?
    • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
I Martingale, Optional sampling theorem
    • Set Theory, Logic, Probability, Statistics
Replies
6
Views
1K
MHB Some basic questions on Graph theory
    • Set Theory, Logic, Probability, Statistics
Replies
2
Views
2K
MHB Understanding the Theorem for Feasible Solutions of Difference Constraints
    • Set Theory, Logic, Probability, Statistics
Replies
15
Views
3K
I On inverse function theorem in Spivak's CoM
    • Calculus
Replies
4
Views
287
Combinatorial Algorithm for Sorting Adjacency Matrices in Polynomial Time
    • Set Theory, Logic, Probability, Statistics
Replies
4
Views
1K
MHB Graph Theory. Decomposition of K_{2n+1} into hamiltonian cycles.
    • Set Theory, Logic, Probability, Statistics
Replies
2
Views
4K
I Understanding Theorem 13 from Calculus 7th ed, R. Adams, C. Essex, 4.10
    • Calculus
Replies
10
Views
2K
I Verifying properties of Green's function
    • Differential Equations
Replies
1
Views
1K

Hot Threads

Recent Insights

Back
Top