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.
1 Answer
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) $$
