I'm trying to understand Ore's Theorem but it seems I'm a bit confused.

"Theorem (Ore; 1960) Let G be a simple graph with n vertices.

If $$\operatorname{deg}(v) + \operatorname{deg} (w) ≥ n$$ for every pair of non-adjacent vertices v, w, then G is Hamiltonian."

Now I'm clearly reading this wrong, but I'll explain my issue. enter image description here

By considering the above graph of 5 vertices, there is a Hamiltonian cycle $\{A,B,C,D,E\}$, yet, for instance, it is the case that $\operatorname{deg}(A) + \operatorname{deg}(C) = 4$ which is clearly less than the 5 vertices in the graph.

Just an example, is it supposed to be the sum of all non-adjacent edges' degrees?

Anyway, any help would be appreciated. Thanks.

  • 10
    $\begingroup$ It's sufficient but not necessary. $\endgroup$ – pointer May 29 '14 at 18:57
  • 1
    $\begingroup$ In case you need more clarification from user121270's comment: If the degree condition holds, the graph is Hamiltonian. But it's not necessarily the case that every Hamiltonian graph also satisfies the degree condition. $\endgroup$ – Perry Elliott-Iverson May 29 '14 at 20:02

The theorem says that;

If $G=(V(G),E(G))$ is connected graph on $n$-vertices where $n≥3]$ so that for $[[x,y∈V(G),$ where $x≠y$, and $deg(x)+deg(y)≥n$ for each pair of non-adjacent vertices $x$ and $y$ then $G$ is a Hamiltonian graph.

The simple meaning of the theorem is that, it says, $$ \forall (\text{non-adjacent vertices pair } v,u ) (\operatorname{deg}(v) + \operatorname{deg} (w) ≥ n) \Rightarrow \text{Graph is Hamiltonian}$$

But this does not imply the reverse of it, that means,

$$ \text{Graph is Hamiltonian} \nRightarrow \\\forall (\text{non-adjacent vertices pair } v,u ) (\operatorname{deg}(v) + \operatorname{deg} (w) ≥ n) $$

  • $\begingroup$ where would Ore's Lemma go wrong if the assumption was deg($u$) + deg($v$) $\geq$ $n-1$? $\endgroup$ – mathmajor Dec 19 '19 at 4:28
  • $\begingroup$ watch this: youtube.com/watch?v=r0IHSXkSSGE&pbjreload=10 Then notice that the neighbhours $H$ of $v_1$ range from $v_2$ to $v_{n-1}$. But the set of vertices $K$ defined by $v_i$ such that $v_{i-1}$ is adjacent to $v_n$ range from $v_3$ to $v_n$. We wanted to find the intersection of $H$ and $K$. but there are a total of $n-1$ vertices in the union. so we need $deg(v_1)+deg(v_n) \geq n$. $\endgroup$ – user 42493 Dec 28 '19 at 15:25

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.