[Math] Question about proof of Ore’s Theorem

graph theoryproof-explanation

Ore's Theorem: If $G$ is a simple graph such that for every pair of non-adjacent vertices $u, v$ of $G$ we have $d(u) + d(v) ≥ |G|$, then $G$ is Hamiltonian.

I am able to follow the classic proof given at ProofWiki quite easily with the exception of one line:

For a given $n≥3$, let $G$ be the graph with the most possible edges such that G is non-Hamiltonian which satisfies (1).

How come this doesn't effectively add another condition to the theorem, proving:

If $G$ is a simple graph such that for every pair of non-adjacent
vertices $u, v$ of $G$ we have $d(u) + d(v) ≥ |G|$ and G is non-Hamiltonian maximal, then $G$ is
Hamiltonian.

Best Answer

The proof is by a form of induction, namely maximal counterexample. Let $S$ denote the set of all graphs on $n$ vertices, that violate the theorem. If $S$ is empty, we are happy as the theorem is true. If $S$ is nonempty, it must be finite, as there are only finitely many graphs on $n$ vertices. Hence, if we consider the ordering on $S$ based on number of edges, we can find a maximal example in $S$. (rest of theorem) Contradiction! Hence $S$ cannot be nonempty.

Related Question