A graph $G = (V, E)$ is semi-Hamiltonian if it possesses a path which uses each vertex of the graph exactly once.
Given is $G = (V,E) $ Show, that if $\deg (u) + \deg (v) \ge |V| - 1 $ for each unjoined pair of verices u and v, then G is semi-Hamiltonian ( it may, of course, also be Hamiltonian). Please help me.
Dirac's theorem states that if $d(v)+d(u) \ge |V|$ for non-adjacent vertices $u,v$ then the graph is Hamiltonian.
Let $G'$ be the graph obtained from $G$ by adding a new vertex $x$ and joining it to all vertices of $G.$
Notice that if $u,v \in V(G')$ are non-adjacent vertices then $d(u) + d(v) \ge |V(G')|+1.$ Hence, $G'$ contains a Hamiltonian cycle $C.$ But then $C-x$ is a Hamiltonian path in $G.$