We have graph $G$ and two not connected vertexes $u,v$ where $$ \deg(u)+\deg(v) \ge n $$ Prove that $G$ contains Hamiltonian circuit $\Leftrightarrow G + uv$ contains Hamiltonian circuit
My approach
$\Rightarrow$
This part is easy because we can use old Hamiltonian circuit and everything will works.
$\Leftarrow $ But I stucked on implication on this side - I tried to divide our graph to $3$ parts: $G_1, G_2, G_3$.
$G_1$ is a part where all vertexes are connected with $u$.
$G_2$ is a part where all vertexes are connected with $v$.
$G_3$ is a part where none of vertexes are connected with $u$ or $v$.
I am not sure what give me information about $\deg(u)+\deg(v) \ge n$ because probably it should be used in that step but currently I don't see that.
If the Hamiltonian cycle does not use the edge $uv$ then it is a Hamiltonian cycle in $G$.
If the Hamiltonian cycle in $G+uv$ uses the edge $uv$, then there is a Hamiltonian path in $G$ going from $u$ to $v$ $$(u=v_1,v_2,\dots, v_n=v)$$ Consider the two sets \begin{align*} P&=\{v_i\mid i\geq 2 \text{ and } uv_i\in G\},\\ Q&=\{v_i\mid i\geq 2 \text{ and } vv_{i-1}\in G\} \end{align*} Note that $P=\Gamma_G(u)$ and $\lvert Q\rvert = \lvert\Gamma_G(v)\rvert$, so $\lvert P\rvert+\lvert Q\rvert\geq n$ and since $P\cup Q\subseteq\{v_2,v_3,\dots,v_n\}$ there is a $v_j\in P\cap Q$. Now $$ (v_j,u,v_2,\dots,v_{j-1},v=v_n,v_{n-1},\dots,v_{j+1},v_j) $$ is a Hamiltonian cycle in $G$.