# Find a graph that does not have a Hamilton circuit

Does there exist a simple graph with n vertices, n≥3 that does not have a Hamilton circuit, yet the degree of every vertex in the graph is at least (n−1)/2?

I know this is not possible if the degree of each vertex is at least n/2 (Dirac's theorem), but I'm not sure about (n-1)/2

Hint: if $G$ has a Hamilton cycle then for any $S \subset V$ we have that $G-S$ has at most $|S|$ components.

The answer, incidentally, is yes, that such graphs exist. Look for a graph with seven vertices, minimum degree three, that has one vertex that when you remove it yields a graph with more than one component.

Edit: Actually, the line graph on three vertices (o-o-o) works.

A bow-tie shape graph with 5 vertices?

• Oddly enough this is almost exactly the graph that I drew; I just used seven vertices instead of five. Commented Apr 9, 2013 at 0:43

If $n=2m+1$ and $m \geq 1$, then the complete bipartite graph $K_{m,m+1}$ has no Hamilton cycle and the minimum degree is $m=(n-1)/2$. [Any Hamilton cycle would alternate between the two parts, implying they must be of equal size.]

In the even $n$ case, "at least $(n−1)/2$" is equivalent to "at least $n/2$", so Dirac's Theorem implies there is a Hamilton cycle. Dropping down by half: If $n=2m+2$ and $m \geq 1$, then $K_{m,m+2}$ has no Hamilton cycle and the minimum degree is $m=(n-2)/2$.