I was reading the proof of this Theorem in the Book "Graphs and Digraphs" of Chartrand (Link to the proof (Page 94-95)) and there's something that I don't understand. This part says:
Hence for each vertex of $\{u_2,u_3,...,u_n\}$ adjacent to $u_i$ there is a vertex of $\{ u_1,u_2,...,u_{n-1}$ not adjacent to $u_n$. Thus, deg $u_n \leq (n-1) -$deg $u_1$ so that $$deg\ u +deg \ v \leq n-1$$ This produces a contradiction; so G is Hamiltonian.
I don't really fully understand how was formulated this inequality. I know that's a contradiction but I don't see it clearly and I want to see it clear. The $n-1$ is because... ? and this part "$-\ deg\ u_1$"?
We assumed that $G$ was non-Hamiltonian and added as many edges as possible to $G$ so that the resulting graph $H$ is non-Hamiltonian. Let $x$ and $y$ be two nonadjacent vertices of $H$ such that $H+xy$ is Hamiltonian. We see that every Hamiltonian cycle of $H+xy$ must contain the edge $xy$. Thus $H$ contains a Hamiltonian $x-y$ path $P=(x=x_1,x_2,...,x_n=y)$. We claim that whenever $x_1x_i$ is an edge of $H$, where $2\leq i\leq n$, then $x_{i-1}x_n$ is not an edge of $H$, otherwise we can produce a Hamiltonian cycle in $H$ which is impossible since $H$ is non-Hamiltonian. Thus it follows that for each vertex in $\{x_2,x_3,..,x_n\}$ that is adjacent to $x_1$, there is a vertex in $\{x_1,x_2,...,x_{n-1}\}$ that is not adjacent to $x_n$ which implies that $\deg x_n\leq (n-1)-\deg x_1$ and so $\deg_Hx+\deg_Hy\leq n-1$. Therefore a contradiction has been produced and $G$ is Hamiltonian.
The proof of this theorem is not obvious at first. When the claim about "whenever $x_1x_i$ is an edge of $H$, where $2\leq i\leq n$, then $x_{i-1}x_n$ is not an edge of $H$" is made, we need to really think about the vertices that are allowed and aren't allowed to be adjacent to $x=x_1$ and $y=x_n$. The reason is because in $H$ we have a Hamiltonian $x-y$ path and if $x_n$ is adjacent to $x_{i-1}$ when $x_1$ is adjacent to $x_i$, where $2\leq i\leq n$, then we have produced a Hamiltonian cycle in $H$ which is impossible. Hence for each vertex in $\{x_2,x_3,..,x_n\}$ that is adjacent to $x_1$, there is a vertex in $\{x_1,x_2,...,x_{n-1}\}$ that is not adjacent to $x_n$. Also, we know that every vertex in $H$ has degree less than or equal to $n-1$. Thus since we know that $x_n$ is not adjacent to $x_1$ since $H$ is non-Hamiltonian, then $\deg x_n\leq (n-1)-\deg x_1$ which implies that $\deg_Hx+\deg_Hy\leq n-1$ which contradicts the fact that $\deg u+\deg v\geq n$ for each pair $u$, $v$ of nonadjacent vertices of $G$. Thus $G$ is Hamiltonian.