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$
  • 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$ – Jeremy Dover Apr 26 '19 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$ – james black Apr 26 '19 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$ – Jeremy Dover Apr 26 '19 at 15:01
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.