[Math] Find a graph that does not have a Hamilton circuit

graph theory

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

Best Answer

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.

Related Solutions

Graph Theory – Showing that No Hamilton Circuit Exists

Suppose that $v$ is a vertex of degree $2$. If $G$ has a Hamilton circuit, that circuit must pass through $v$, so it must include both of the edges incident at $v$. In particular, if the configuration

              o----o----o  
              u    v    w

occurs anywhere in $G$, it must be part of any Hamilton circuit in $G$. Such a circuit must be a circuit, so it must include some other path from $u$ to $w$ as well. This can be useful in proving that a graph does not have a Hamilton circuit: if there is no other path between $u$ and $w$ in $G$, then $G$ cannot have a Hamilton circuit.

[Math] If a graph has a Hamilton Path starting at every vertex, must it contain a Hamilton Circuit

The Petersen graph is a counter example to your problem. All vertices are similar and it is easy to find an hamiltonian path. But there is no hamiltonian cycle in this graph.

I think it is the smallest example but I do not have a proof.

You can easily prove that all vertices must have degree at least 2 (if a vertex has degree 1, then there is no hamiltonian path starting from its unique neighbor).

Hence the smallest counter example has all vertices of degree at least 2. Furthermore, it has no cut vertices (there is no hamiltonian path starting from a cut vertex) and no bridge edge.

Best Answer

Related Solutions

Graph Theory – Showing that No Hamilton Circuit Exists

[Math] If a graph has a Hamilton Path starting at every vertex, must it contain a Hamilton Circuit

Related Question