7
$\begingroup$

Dirac's theorem states that if degree of each vertex of a graph $G=(V,E)$ is not less than $|V|/2$, then it has Hamiltonian cycle. It is less known, but still known and not so hard to prove (though I do not know the reference other than competition problem) that if all degrees are exactly $(|V|-1)/2$, the graph still have Hamiltonian cycle. So the question.

Let $G$ be a graph with $2n+1$ vertices and all degrees at least $n$ but without Hamiltonian cycle. What is minimal possible number of edges in $G$? There are two examples with $n(n+1)$ edges: $K_{n,n+1}$ and two $K_{n+1}$'s glued by a vertex. Maybe, this is least possible actually?

UPDATE. It looks that what actually is proved in the result to which I refer is that the graph on $2n+1$ vertices without Hamiltonian cycle and all degrees at least $n$ either contains $K_{n,n+1}$ or coincides with two $K_{n+1}$'s glued by a vertex. This answers the question, if anybody is interested I may leave a proof here, if not, just remove the question.

$\endgroup$
  • 2
    $\begingroup$ I'm interested. Note that Posa's Theorem implies that there are at least $n+1$ vertices of degree exactly $n$. $\endgroup$ – Tony Huynh Sep 23 '15 at 16:32
  • 1
    $\begingroup$ Regarding "all degrees exactly $(|V|-1)/2$": In the regular case a much stronger result was proved by Bill Jackson. It is enough if $|V| \ge 3d+2$ where $d$ is the degree. $\endgroup$ – Brendan McKay Sep 23 '15 at 23:36
  • $\begingroup$ @BrendanMcKay you mean opposite inequality? But why it can not be disconnected? Or if we require it to be connected, why it can not have cut vertex? Something must be required additionally. $\endgroup$ – Fedor Petrov Sep 24 '15 at 6:04
  • 1
    $\begingroup$ @Fedor Oops, yes, I got it backwards. I also forgot that 2-connectivity is needed. The correct statement is "Every 2-connected, $k$-regular graph on at most $3k$ vertices is hamiltonian." JCT(B) 29 (1980) 27-46. $\endgroup$ – Brendan McKay Sep 24 '15 at 7:48
  • $\begingroup$ I see. Nice result, is there any simplification of the proof? It looks quite technical. $\endgroup$ – Fedor Petrov Sep 24 '15 at 10:47
3
$\begingroup$

Let $G$ be a graph with $2n+1$ vertices and all degrees at least $n$ but without Hamiltonian cycle. Consider two cases.

1) There is a cycle $C=x_1\dots x_{2n}x_1$ of length $2n$. Let $y$ be the vertex not in this cycle. If it is joined with two consecutive vertices in $C$, then we have a Hamiltonian cycle. Thus $y$ is joined, say, with $x_1,x_3,\dots,x_{2n-1}$. Replace $C$ to a new cycle, replacing fragment $x_{2k-1}x_{2k}x_{2k+1}$ to $x_{2k-1}yx_{2k+1}$. Apply the same argument, now $x_{2k}$ plays role of $y$. We see that $x_{2k}$ must be joined with $x_{2i-1}$ for all possible indices $2i-1,2k$. It follows that $G$ contains $K_{n,n+1}$ ($x_1,x_3,\dots,x_{2n-1}$ is first part and $y,x_2,x_4,\dots,x_{2n}$ the second part. It may contain also arbitrary set of edges between vertices of the first part.

2) There is no such a cycle. Consider Hamiltonian path $P=x_1\dots x_{2n+1}$ in $G$. Then $x_1$ is joined with some (at least) $n$ vertices in $P$. If $x_1$ is joined with $x_k$, then $x_{2n+1}$ can not be joined with $x_{k-1}$, nor with $x_{k-2}$. If for some $k$ it appears that $x_1$ is joined with $x_k$, $k>2$, but not with $x_{k-1}$, we get already $n+1$ forbidden vertices for $x_{2n+1}$. Thus $x_1$ must be joined with $x_2,\dots,x_{n+1}$ and $x_{2n+1}$ with $x_{n+1},\dots,x_{2n}$. Now for any $k=2,\dots,n$ change path to $x_kx_{k-1}\dots x_1x_{k+1}\dots x_{2n+1}$. Repeat the same argument. We see that $x_1,\dots,x_{n+1}$ form a clique, as well as $x_{n+1},\dots,x_{2n+1}$. Thus $G$ coincides with two cliques of size $n+1$ glued by their common vertex. Adding any edge produces a Hamiltonian cycle.

$\endgroup$
  • 2
    $\begingroup$ It seems to me that the existence of a cycle of length $\geq 2n$, provided that all degrees are $\geq n$ and there is no cut vertex, is proved in Dirac's paper containing his theorem. $\endgroup$ – Ilya Bogdanov Sep 23 '15 at 21:35

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.