proof of Ore's Theorem There was a part in Proofwiki's proof that I didn't understand. (http://www.proofwiki.org/wiki/Ore%27s_Theorem)

Although it does not contain a Hamilton cycle, G has to contain a Hamiltonian path (v1,v2,…,vn).
Otherwise it would be possible to add further edges to G without making G Hamiltonian.

The proposition here is "if G doesn't contain a Hamiltonian path then it is possible to add more edges to G without creating a Hamilton cycle."
I got started by separating two cases where G doesn't contain a Hamiltonian path;
(1)G contains a path which omits at least one vertex.
(2)G contains a walk which goes through every vertex but at least one vertex is repeated.
How do I proceed from here?
 A: By construction $G$ is the graph with the most possible edges that does not contain a Hamiltonian cycle. This means that adding another edge anywhere will create a Hamiltonian cycle. Recall that a path is just one edge from a cycle - in a path the beginning and ending nodes are distinct but otherwise. So a Hamiltonian path is just one edge from a Hamiltonian cycle.
If $G$ did not contain a Hamiltonian path, then you could keep adding edges until you created a Hamiltonian path (or multiple Hamiltonian paths), so $G$ would not be the graph with the most possible edges.
Don't think about walks. There are an infinite number of possibilities for walks - they will just confuse you.
A: Suppose that $G$ does not contain a Hamilton path $\langle v_1,\dots,v_n\rangle$. Let $P=\langle v_1,\dots,v_m\rangle$ be a maximal Hamilton path in $G$, and let $v$ be any vertex of $G$ not in the path $P$. Add the edge $\{v_m,v\}$ to $G$, and call the resulting graph $G'$. $G'$ has the same vertex set as $G$, and it still satisfies $(1)$ of the ProofWiki article. Moreover, $G'$ has no Hamilton circuit: such a circuit would necessarily contain the new edge, and removing that edge would leave a Hamilton path in $G$, which we assumed does not exist. Finally, $G'$ has one more edge than $G$, which contradicts the choice of $G$ as a counterexample with the maximum number of edges among all counterexamples on $n$ vertices.
