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?

  • 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 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 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 at 15:01

Your Answer

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

Browse other questions tagged or ask your own question.