Proving that a graph of a certain size is Hamiltonian

For any graph with order $n \geq 3$, given that its size is $$m \geq \frac{\left(n-1\right)(n-2)}{2} + 2,$$ show that the graph is Hamiltonian.

I know that if I can show that the degree sum of any two non-adjacent vertices is $\geq n$, then I'd be done.

Likewise, if I could show that the above somehow implied that the degree of every vertex in the graph is $\geq n/2$, I'd also be done. However, I cannot see how to get to either one of those given the information I have. I have been trying the following: assuming that there exists two non-adjacent vertices $u$ and $v$ whose degree sum is $\leq (n-1)$, then $$2m = \sum d\text{(other vertices))} + d(u) + d(v) \leq \sum d(\text{other vertices)} + (n-1).$$ If I could show that this implied that $$2m < \left(n-1\right)(n-2) + 4,$$ I would have a contradiction, thereby proving that the graph is Hamiltonian. However, I have not been able to show this, so I am thinking it is the wrong approach.

A graph on $n$ vertices can have at most $m=\frac{n(n-1)}{2}$ edges, $(K_n)$. The graph given in the problem statement, $G_n=(V,E)$, with $|V|=n$ and $|E|=m$ has $m\geq \frac {(n-1)(n-2)+4}{2}$ edges. Because $\frac{n(n-1)}{2}-\frac {(n-1)(n-2)+4}{2}=n-3$, any $G_n$ can be created from $K_n$ by deleting exactly $n-3$ edges from $K_n$.

A graph is hamiltonian if its closure, cl$(G)$, is hamiltonian. Consider the effects of subtracting an edge from $K_n$. Each subtracted edge reduces the degree of two vertices by one.

You can proceed by induction on $\delta (G)$.

If all the subtracted edges are adjacent to a single vertex then that vertex will have degree $(n-1)-(n-3)=2$ thus $\delta(G_n)=2$ . Each other vertex in $G_n$, with $\delta(G_n)=2$ will have degree $(n-1)-1$. $n-2+2=n$ so the graph will close to $K_n$ and $G_n$ is hamiltonian.

If $\delta (G)=3$ the next smallest degree vertex in $G_n$ can have degree $(n-1)-1-1=(n-3)$. $n-3+3=n$ so the graph will close to $K_n$ and $G_n$ is hamiltonian.

If $\delta (G)=k+1$ the next smallest degree vertex in $G_n$ can have degree $(n-1)-k$. $n-1-k+(k+1)=n$ so the graph will close to $K_n$ and $G_n$ is hamiltonian.

• How to show that if $\delta (G)=k+1$, then the next smallest degree vertex in $G_n$ can have degree $(n-1)-k$? – pipi Oct 23 '12 at 1:37

Proof by induction on $n$.

Let $G$ be a graph of order $n$ and size $m$ (given). Denote the maximum degree of a vertex of G by $\Delta$ and the average degree by $\delta$. Then

$$\delta = \frac{2m}{n} \geq \frac{(n-1)(n-2)+4}{n} \geq n-3+\frac{6}{n}$$

$\Delta \geq \delta$ and $\Delta\in \mathbb{Z}$, so $\Delta \geq n-2$. Let $v$ be a maximum degree vertex of G.

$d(v)$ is $n-1$ or $n-2$.

Case 1: $d(v)=n-2$

$$e(G-v)= m-d(v)\geq \frac{(n-2)(n-3)}{2}+2$$

So, by induction hypothesis, $G-v$ contains a Hamiltonian cycle. Two adjacent vertices in this cycle are neighbors of $v$, so add v to the cycle and we are done.

Case 2: $d(v)=n-1$

Now the above doesn't quite hold, since $G-v$ contains 1 fewer edge than required. No problem! Let $H$ be $G-v$ with an arbitrary edge added (call this $jk$. By induction hypothesis, $H$ is Hamiltonian. If this cycle doesn't contain the added edge we are done, as in Case 1. Otherwise, deleting $jk$ gives a Hamiltonian path in $G-v$ from $j$ to $k$. $j\sim v$ and $k\sim v$, since $d(v)=n-1$, so we have a Hamiltonian cycle, as required.

Base case: easy.

Edit: A general tip

I find it useful in problems like this to see how the numbers arise. Consider briefly why any fewer edges are insufficient.

You were on the right path. Possibly, you can do it way easier than I just did. However, this was how it came to mind for me. Note that I answered the question 'for higher $n$'. Perhaps it also works for $n \geq 3$, but I did not verify that. I'm sure that with more careful arguments (or simply bruteforce for $n=3$ and $n=4$) it should work.

Given a graph $G=(V,E)$ on $n$ vertices and $m$ edges, with $m = (n-1)(n-2)/2+1$. Suppose there is one pair of non-adjacent vertices $a$ and $b$ such that $d(a)+d(b) \leq n-1$ and that all other pairs are either adjacent or the sum of their degrees is at least $n$.

Find a set of pairs of distinct vertices $(u_1,v_1), ... ,(a_k,v_k)$ such that $(u_i,v_i)$ are non-adjacent and all pairs (including $(a,b)$) are pairwise disjoint e.g. each vertex is in at most one pair.

Then, the set of vertices $C$ in the graph that are in no pair, $C := V \setminus ( \cup_{1 \leq i \leq k} u_i \cup_{1 \leq i \leq k} v_i \cup \{a,b\} )$ induces a clique in $G$.

Let $H$ be a hamiltonian cycle in $G[V \setminus C]$. Let $w$ and $x$ be two adjacent vertices in $H$. Then, if there are two distinct vertices $y$ and $z$ in $C$ such that $wy \in E$ and $xz \in E$, there is an hamiltonian cycle for $G$. Therefore, if $w$ has one edge to $C$ and $x$ at least one, we are done. For a contradiction, assume that for all adjacent pair of vertices $w$ and $x$ in $H$, that either $x$ or $w$ has degree $0$ towards $C$. Then the total degree of this graph is at most*:

• Edges in $G[H]$ is at most $(n-|C|)(n-|C|-1)/2$
• Edges in $G[C]$ is $|C|(|C|-1)/2$
• Edges between $H$ and $C$ is at most $(|H|/2) \cdot |C| = ((n-|C|)/2) \cdot |C|$

However, we know that we have $m = (n-1)(n-2)/2+1 = (n-|C|+|C|-1)(n-|C|+|C|-2)/2 +1$ $= (n-|C|)^2 + 2(n-|C|)|C|-3(n-|C|)-3|C|+|C|^2+2$ edges.

Comparing the quantities we find out that this is a contradiction. Therefore, it is sufficient to find a hamiltonian cycle in $G[V \setminus C]$ and we will focus on that from this point.

*The other case is both have degree $1$ towards $C$, but the total number of edges is lower, so it's the easier case.

Writing out the idea that you also wrote in your question:

Each vertex, apart from $a$ and $b$ has degree at most $n-2$, so therefore we have at most $((n-2)(n-2)+n-1) /2)$ edges in the graph.

• $(n-2)(n-2)+n-1 \geq 2m = (n-2)(n-1) + 4$
• $n^2-4n+4+n-1 \geq 2m = n^2-3n+2 + 4$
• $n^2-3n+3 \geq 2m = n^2-3n+6$

Which is a contradiction, therefore for any two non-adjacent vertices the sum of their degrees is at least $n$.