Let $G$ be a graph on $n$ vertices with size at least ${n\choose 2} - (n-2)$. Show that $G$ is Hamiltonian. What is the unique Extremal graph?

The first part I did. I even know the Extremal graph should be $K_{n-1}$ together with a vertex of degree 1. The way I have been trying to prove this is by considering $K_n$ and removing edges, specifically, $n-2$ edges. My goal is to show that the only way to avoid a Hamiltonian graph is to do this by removing all the edges from one vertex.

A graph is Hamiltonian if it's minimal degree is $n/2$, by Dirac's Theorem, so I need to remove $k$ edges from, say a vertex $x$ so that $d(x) = \delta(G) < n/2$. In $K_n$, the degree of $x$ is $n-1$, so I need to remove $\lceil(n-2)/2\rceil$ edges incident with $x$. Then, there are at most $(n-2)/2$ edges left to remove from $n-1$ vertices, so each of these have degree at least $n/2$.

Now I have a graph with a vertex of degree $d(x)<n/2$ and a subgraph with $n-1$ vertices and a Hamilton cycle. I just need to show I can extend this to a Hamilton cycle containing $x$.

My thought was to follow a proof of Dirac's Theorem and construct a maximal path containing $x$. This must contain all the neighbors of $x$, or else it is not maximal. Where I am struggling is how do I guarantee that $x$ is not an end vertex of this path and actually find a cycle?

  • $\begingroup$ It's better to rewrite so: suppose you have $K_{n} - (n - 2)$, select vertex with the largest number of delete edges. So if you proof that Dirac's Theoren is applicable for $G\v$, you will prove this. $\endgroup$ – openspace Feb 20 '16 at 16:50
  • $\begingroup$ Dirac's Thereom does not need to apply. I have already shown that I can construct a graph where the largest number of delete edges gives me a minimal degree less than $n/2$. $\endgroup$ – Henry Feb 20 '16 at 17:13
  • $\begingroup$ But you should use fact that you could delete edges from different vertices $\endgroup$ – openspace Feb 20 '16 at 17:15
  • $\begingroup$ If I delete them as evenly as possible, every vertex has degree n-1 or n-2. In either case, the graph is Hamiltonian, so I don't want to delete them in this way. How do you suggest I delete them? $\endgroup$ – Henry Feb 20 '16 at 17:21
  • $\begingroup$ If you delete $n-4$ edges from first vertex $2$ from other. What it will be? $\endgroup$ – openspace Feb 20 '16 at 17:24

We prove the contrapositive. If $G$ is complete, then we are done. Suppose not. Then there are nonadjacent vertices $x$ and $y$. Set $G'=G-x-y$. Note that $${n\choose 2} - {n-1\choose 2} = \frac{(n-1)[n-(n-2)]}{2} = n-1$$ so that $${n\choose 2} - (n-2)= {n-1\choose 2}+1.$$ Since we assume that $e(G) > {n\choose 2} - (n-2)= {n-1\choose 2}+1,$ it follows that $${n-1\choose 2}+1- d(x)-d(y) < e(G') \leq {n-2\choose 2},$$ where the upper bound comes from the complete graph on $n-2$ vertices. Algebra reveals that \begin{align*} {n-1\choose 2}-{n-2\choose 2}+1&= \frac{(n-2)[(n-1)-(n-3)]}{2} +1\\ &= n-1 < d(x) + d(y), \end{align*} and this is equivalent to $$d(x) +d(y) \geq n,$$ which is the condition for $G$ to be Hamiltonian.

To see the extremal graph is unique, suppose $G$ is extremal. Since there are ${n\choose 2}-(n-2)$ edges, and $G$ is not Hamiltonian, we must have that $\delta(G) <n/2$. If $d(x) = \delta(G)$, we know \begin{align*} d(x) &=n-1-k\\ &<n/2 \end{align*} Thus, \begin{align*} 2n-2-2k &<n\\ \frac{n-2}{2} &< k. \end{align*} However, there is at most one vertex of this degree. If not, then we subtracted $(n-2)/2$ edges from at least two vertices in $K_n$, which is impossible. Thus, considering $G'=G-x$, we see that $\delta(G') \geq n/2$, so $G'$ is Hamiltonian.

Suppose that $d(x) \geq 2$. Take a maximal path in $G$ containing $x$, say $P=x_0x_1\cdots x_m$, where $x_0,x_m\in G'$. Such a path must exist if $d(x) \geq 2$. Moreover, we see that all the neighbors of $x_0$ and $x_m$ must be in $P$. At least $n/2$ of the vertices of $P-x_0$ are adjacent to $x_0$ and at least $n/2$ in $P-x_m$ are adjacent to $x_m$. Since $d(x_0)+d(x_m) \geq n$ and the length of $P$ is at most $n$, we see that, for some $x_i$ with $0\leq i\leq m-1$, $x_ix_m$ and $x_0x_{i+1}$ are edges in $G$. The path $x_0x_{i+1}\cdots x_{m-1}x_mx_i\cdots x_1x_0$ is a Hamilton cycle in $G$, contradicting the fact that $G$ is extremal. Thus, no such path exists, contradicting the fact that $d(x) \geq 2$. Thus, $d(x) \leq 1$. Clearly $d(x) \neq 0$ and, therefore, we must have removed $n-2$ vertices from $x$ in $K_n$ to construct $G$. As every edge removed from $x$ in $K_n$ while constructing $G$ decreases the degree of one vertex by 1, and each vertex has only one edge joining it to $x$, the graph $G'$ is $K_{n-1}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.