To prove the statement that if $G + uv$ is Hamiltonian, then $G$ is also Hamiltonian, we will use the concept of cycle exchanges. Here's a step-by-step proof:

Definitions and Setup

1. Graph $G$: A graph with order $n \geq 3$.
2. Vertices $u$ and $v$: Two distinct nonadjacent vertices in $G$ such that $\deg(u) + \deg(v) \geq n$.
3. Graph $G + uv$: The graph obtained by adding the edge $uv$ to $G$.
4. Hamiltonian Cycle: A cycle that visits every vertex exactly once.

Proof

1. Assumption: Assume $G + uv$ is Hamiltonian. This means there exists a Hamiltonian cycle $C$ in $G + uv$.

2. Properties of $C$: Since $C$ is a Hamiltonian cycle in $G + uv$, it includes the edge $uv$. The cycle can be represented as: $C = u \to v \to P_1 \to u$ where $P_1$ is the path covering all the vertices except $u$ and $v$.

3. Subdivide $C$: Consider $C$ without the edge $uv$. This cycle $C$ in $G + uv$ can be split into two paths: $P_1 = u \to x_1 \to x_2 \to \ldots \to x_k \to v$ and $P_2 = v \to y_1 \to y_2 \to \ldots \to y_{n-k-2} \to u$

4. Degrees Condition: Given that $\deg(u) + \deg(v) \geq n$, there must be enough vertices adjacent to either $u$ or $v$ in $G$.

5. Cycle Exchange Argument:

   • Because $\deg(u) + \deg(v) \geq n$, there is at least one vertex $w$ in $P_1$ adjacent to $u$ or in $P_2$ adjacent to $v$.
   • If such a vertex $w$ exists in $P_1$ and is adjacent to $u$, consider the path from $u$ to $w$ and back to $v$ along $P_1$. We then form a cycle excluding $v$ initially but including $v$ later in the sequence, showing a new cycle formation without $uv$.
   • Similarly, if $w$ exists in $P_2$ adjacent to $v$, construct the path from $v$ to $w$ and back to $u$ along $P_2$. This forms a new cycle excluding $u$ initially but including $u$ later in the sequence.

6. Conclusion: By performing these exchanges, we can reintroduce $u$ and $v$ in a way that cycles around the rest of the vertices, ensuring that the initial assumption that $G + uv$ being Hamiltonian extends to $G$ as well.

Thus, if $G + uv$ contains a Hamiltonian cycle, $G$ itself must also contain a Hamiltonian cycle. This concludes the proof.

Do you want details or have any questions?

Here are some related questions you might find interesting:

1. What is a Hamiltonian path, and how does it differ from a Hamiltonian cycle?
2. Can you explain Dirac's theorem and its implications for Hamiltonian cycles?
3. How do Eulerian paths and cycles differ from Hamiltonian ones?
4. What are some common methods for finding Hamiltonian cycles in graphs?
5. What is the significance of the degree condition in the context of Hamiltonian graphs?

Tip: When analyzing graph properties, pay close attention to vertex degrees and adjacency conditions, as they often provide crucial insights into the structure and behavior of the graph.