Proving that a graph of a certain size is Hamiltonian

Question

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.

Answer 1

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$.

Answer 2

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.

Answer 3

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.