Bondy and Chvátal Thm (Hamiltonian Cycles) Proof Question

Question

I'm looking over the proof of the Bondy and Chvátal Thm here. I understand everything in the proof until it gets to the point where it says, "Thus, $d⁢(x_n)≤(n-1)-d⁢(x_1)$."

$\textbf{Question:}$ How do we know "$d⁢(x_n)≤(n-1)-d⁢(x_1)$" ?

I'm assuming it has something to do with the preceding sentencence where it states, "If $x_i$ is adjacent to $x_1 $($2≤i≤n$) then $x_{i-1}$ is not adjacent to $x_n$", but I do not see why that allows us to conclude that. Any help would be greatly appreciated.

Answer 1

Background on Bondy-Chvatal, for convenience of future readers

The Bondy-Chvatal theorem says:

Let $G$ be a graph on $n$ vertices, and let $u,v$ be two non-adjacent vertices of $G$ with $\deg(u) + \deg(v) \ge n$. If $G + uv$ (the graph we get by adding edge $uv$ to $G$) has a Hamiltonian cycle, then so does $G$.

(In other words, we did not need $uv$ to have a Hamiltonian cycle: the magic was inside us all along.)

To prove this, let $C$ be a Hamiltonian cycle of $G + uv$. If $C$ does not use the edge $uv$, then $C$ is a Hamiltonian cycle of $G$ and we are done. Otherwise, deleting $uv$ from $C$ leaves a Hamiltonian path: a path $P = (x_1, x_2, \dots, x_n)$ with $x_1 = u$ and $x_n = v$.

Now our goal is to use $P$ to find some other Hamiltonian cycle in $G$.

(The planetmath proof is written as a proof by contradiction, but I think that's unnecessarily complicated. The idea is the same either way.)

The answer to the question starts here

The way I like to continue the proof is this:

• Let $S = \{i \in [n-1] : x_i \sim x_n\}$. That is, $S$ contains the indices of all vertices in $P = (x_1, x_2, \dots, x_n)$ which are adjacent to $x_n$. We have $|S| = \deg(x_n) = \deg(v)$ because the elements of $S$ correspond to neighbors of $x_n$.
• Let $T = \{i \in [n-1] : x_1 \sim x_{i+1}\}$. That is, $T$ contains the indices of all vertices in $P$ which come before a vertex adjacent to $x_1$. We have $|T| = \deg(x_1) = \deg(u)$ because the elements of $T$ correspond to neighbors of $x_1$.

If there is some $i \in S \cap T$, then $x_ix_n$ and $x_{i+1}x_1$ are edges, so $(x_1,x_2, \dots, x_i, x_n, x_{n-1}, \dots, x_{i+1})$ is a Hamiltonian cycle. In this case, we're done.

Otherwise, $S \cap T = \emptyset$. In this case, $S$ and $T$ are disjoint subsets of $[n-1]$, so $|S| + |T| \le n-1$.

But $|S| = \deg(x_n)$ and $|T| = \deg(x_1)$, so we conclude $\deg(x_1) + \deg(x_n) \le n-1$, which is the inequality you wanted to understand. It contradicts our assumption that $\deg(u) + \deg(v) \ge n$, so $S \cap T = \emptyset$ cannot hold.

Answer 2

I'm going to post an answer here too just for notes even though I accepted an answer already. We know $d(x_n)\leq |V^{\neq x_n}|\implies d(x_n)\leq n-1$ simply by getting rid of the vertex $x_n$ from the set of all vertices. Since for any $i$ where $2≤i\leq n$, we know if $x_i\in N(x_1)$ that $x_{i-1}\notin N(x_{n})$ (we are able to get rid of $x_{i-1}$ from this set too just like before). We continue this process for every vertex in the neighborhood of $x_1$ (in turn deleting some other vertex somewhere else) to conclude $d(x_n)\leq n-1-d(x_1)$. However, we know $d(x_1)+d(x_n)\leq n$ must have been true before adding edge $\{u, v\}$ (as we added it to its closure). Thus, we know $d(x_1)+d(x_2)\leq n-1<n\leq d(x_1)+d(x_n)$. This is a contradiction.