1
$\begingroup$

Proof that if graph has $\frac{(n-1)(n-2)}{2} + 2$ edged then contains hamiltonian cycle

I think that it is good to use there induction:
Let check base of induction. For $ n= 3 $ I have $$ |E| = \frac{2\cdot1}{2}+2 = 3 \text{ and }n \text{ vertices }$$ so this is just triangle and triangle contains hamiltonian cycle.

Assume that $$ \text{if graph with |V| = n has }\frac{(n-1)(n-2)}{2} + 2 \text{ edges then contains hamiltonian cycle } $$ Proof that $$ \text{if graph with |V| = n+1 has }\frac{n(n-1)}{2} + 2 \text{ edgesthen contains hamiltonian cycle } $$

In this step I checked how many edges I have added: $$\frac{1}{2} (n-1) n-\frac{1}{2} (n-2) (n-1) = n-1 $$ Now I should show that if I add $n-1$ edges in any way to my first graph, it will have hamiltonian cycle, but there I have stucked

$\endgroup$
1
$\begingroup$

Let $G$ be a graph with $n$ vertices and at least $\frac{(n-1)(n-2)}2+2$ edges. Suppose we find a vertex $v$ with $\frac{n-1}2<\rho(v)<n-1$. Then by removing $v$, we obtain a graph on $n-1$ vertices and (due to the right inequality) at least $\frac{(n-2)(n-3)}2+2$ edges. We may assume by induction that this has a Hamiltonian cycle. By the left inequality, $v$ is neigbour to more than half the vertices, hence to two consecutive vertices in this cycle and we can insert $v$ between those, thus finding a Hamiltonian cycle for the original graph.

Therefore, we may assume that all vertices have either $\rho(v)=n-1$ or $\rho(v)\le \frac{n-1}2$. If there are $k$ vertices of degree $\le\frac{n-1}2$, we count at most $$\frac{(n-k)(n-1)+k\frac{n-1}2}2 =\frac{(n-1)(2n-k)}4$$ edges. Hence $$ \frac{(n-1)(2n-k)}4\ge \frac{(n-1)(n-2)}2+2,$$ or $$\tag1k\le 4-\frac 8{n-1}.$$ We conclude $k\le 3$. But if $v$ is one of these $k$ vertices, we also have $\frac{n-1}2\ge\rho(v)\ge n-k$, or $$\tag2 k\ge \frac{n+1}2.$$ Combined, $4-\frac 8{n-1}\ge \frac{n+1}2 $, or after rearranging $$ 0\ge {n^2}-8n+23=(n-4)^2+7,$$ which is absurd.

$\endgroup$

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.