Prove that a graph G on n vertexes has a Hamiltonian path if for all non-adjacen

Question

Prove that a graph G on n vertexes has a Hamiltonian path if for all non-adjacent vertexes u and v, deg(u) + deg(v) >= n - 1. (Hint: consider augmenting a new vertex and edges base on G, and apply Ore's theorem).
if you get it right ill give you all of my points Prove that a graph G on n vertexes has a Hamiltonian path if for all non-adjacent vertexes u and v, deg(u) + deg(v) >= n - 1. (Hint: consider augmenting a new vertex and edges base on G, and apply Ore's theorem).
if you get it right ill give you all of my points

Explanation / Answer

Use Ore's theorem "Let G be a simple graph of order n>=3 such that, for every pair of distinct non adjacent vertices and u and v, deg(u) + deg(v) >= n . Then G is a Hamiltonian graph." If we construct H, then each vertex increases in degree by 1. Hence now deg >= 1/2(p-1) + 1 =.5p + .5 this is equivelent to saying deg>=.5 (p+1). Hence for any two verticies the sum of they're degree will be >= (p+1) our graph has p+1 verticies now so this satisfies the conditions for Ore's theorem. So H is hamiltonian. Take a cycle, and take away w. This is now a path in G.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.