0
$\begingroup$

I'm trying to show that a connected graph which has order >=3, and having the following inequality is Hamiltonian:

degG(x) + degG(y) >= n   x and y are two non-adjacent vertices

I know that Dirac's theorem will be helpful here, but I really don't know how to apply it. (Dirac's theorem: Let G be a graph of order n>= 3. If the minimum degree of graph G is >= n/2, then G is Hamiltonian).

Could you guys give me any hints? Thanks!

Improve this question
$\endgroup$
4
  • $\begingroup$ If memory serves me right, it's the other way around - the statement you are trying to prove implies Dirac's theorem (which it clearly does), not is implied. Though I might be wrong here. $\endgroup$
    – Wojowu
    Commented Aug 14, 2016 at 17:03
  • $\begingroup$ I think you should be able to modify the proof of Dirac's theorem to imply your statement. $\endgroup$
    – Jan-Christoph Schlage-Puchta
    Commented Aug 14, 2016 at 17:20
  • $\begingroup$ Googling suggests that this theorem is attributed to Ore, and can be found here: Ore, O. A note on Hamiltonian Circuits. Amer. Math. Monthly 67 (1960), 55. $\endgroup$
    – Hugh Thomas
    Commented Aug 15, 2016 at 2:21
  • $\begingroup$ @KevinZ: Perhaps, ask such questions on math.stackexchange.com $\endgroup$
    – Moritz
    Commented Aug 15, 2016 at 16:37

1 Answer 1

Reset to default
3
$\begingroup$

Your result is true. It is a generalization of Dirac's Theorem known as Ore's Theorem.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Nice link! What is en.m.wikipedia as opposed to en.wikipedia? $\endgroup$
    – Włodzimierz Holsztyński
    Commented Aug 14, 2016 at 22:22
  • 1
    $\begingroup$ @WłodzimierzHolsztyński I think the mobile version. I did copy and paste the url from on my phone. I changed the link, it should now go to the regular site (and mobile browsers should redirect appropriately). $\endgroup$
    – John Machacek
    Commented Aug 14, 2016 at 22:25

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