1
$\begingroup$

Let a n-vertex graph such that every pair of not adjacent vertices a & b has degree(x) + degree(y) $\geq$ n. Show the graph contains a Hamiltonian cycle.

By dirac's thm, a simple graph with n vertices (n ≥ 3) is Hamiltonian if every vertex has degree n / 2 or greater. How would i relate this thm to the question?

$\endgroup$
3
  • 2
    $\begingroup$ Try to mimic the proof of Dirac's theorem using the given weaker degree condition. The key point is finding a vertex in the middle of the longest path that both end points are adjacent to. $\endgroup$ Commented Apr 26, 2019 at 13:50
  • $\begingroup$ how do i sub the new conidition to the proof of dirac in the step of finding vertex j in the longest path? $\endgroup$ Commented Apr 26, 2019 at 14:51
  • $\begingroup$ That is the crux of the problem. See how the condition $deg(v) \ge \frac{n}{2}$ is used in the proof of Dirac's theorem to ensure two sets of vertices intersect, and try to extend it to the weaker condition in the problem. $\endgroup$ Commented Apr 26, 2019 at 15:01

1 Answer 1

1
$\begingroup$

I guess non-adjacent vertices should be named $x$ and $y$. Then you ask to prove Ore’s theorem.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .