# Ore's Theorem - Graph Theory

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.

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.

• It's sufficient but not necessary. – pointer May 29 '14 at 18:57
• 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. – Perry Elliott-Iverson May 29 '14 at 20:02

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}$$
$$\text{Graph is Hamiltonian} \nRightarrow \\\forall (\text{non-adjacent vertices pair } v,u ) (\operatorname{deg}(v) + \operatorname{deg} (w) ≥ n)$$
• where would Ore's Lemma go wrong if the assumption was deg($u$) + deg($v$) $\geq$ $n-1$? – mathmajor Dec 19 '19 at 4:28
• 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$. – user 42493 Dec 28 '19 at 15:25