Ore's Theorem - Graph Theory

Question

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.

Answer 1

Following observation is motivated by the video on YouTube Channel Wrath of Math.

Theorem of Ore:

If $G$ is a simple graph with $n$ vertices with $n \geq 3$ such that $deg(u)+deg(v) \geq n$ for every pair of nonadjacent vertices $u$ and $v$ in $G$, then $G$ has a Hamilton circuit.

For the sake of contradiction, we make the following statement. If $G$ is a simple graph with $n$ vertices with $n \geq 3$ such that $deg(u)+deg(v) \geq n$ for every pair of nonadjacent vertices $u$ and $v$ in $G$, then $G$ does not have a Hamilton circuit. Let’s successively add an edge to $G$ one at a time to make the $G^{’}$ that can be Hamiltonian if we add a single edge. That is, $G_{last} = G^{’} + e, \text{ where } e \in E^{’} \text{ in } G_{last} = (V, E^{’})$ and $G_{last}$ is a Hamiltonian. If $e$ is incident with $u$ and $v$ where $u,v \in V$, then there must be a Hamilton path from $u$ to $v$: $(u=x_1,x_2,...,v = x_n )$. Otherwise, we would not be able to construct a Hamiltonian circuit by splicing $u$ into $v$. Now considering the Hamilton path above we are able to state that if $u$ is adjacent to $x_i$ for $2 \leq i \leq n$, then $v$ cannot be adjacent to preceding vertex of $x_i$, that is, $x_{i-1}$, that forms a Hamilton circuit. One can observe the following figure for the sake of illustration: enter image description here

Considering of $max_{v \in V} deg(v) \leq n -1$, we can say that $deg(v) \leq n - 1 - deg(u)$. Because if $u$ has adjacent vertices among the vertices in Hamilton path above, then $v$ cannot be adjacent with the preceding vertices of $N(u)$ in that path, where $N:V\rightarrow V$. If we add deg(u) to the both sides of inequality, then we get $$deg(v) + deg(u) \leq n -1,$$ that contradicts with the statement mentioned in the definition. That is, sum of the degrees of nonadjacent vertices cannot be strictly greater than the number of vertices in graph. So we reached to the contradiction.