Graph implications
If a graph is simple and hypohamiltonian, which of these statements must be true?
A. It is hamiltonian
B. It is nonplanar
C. It is 3-connected
Definitions:
A
simple
graph has no loops or multiple edges.
A
hamiltonian cycle
of a graph is a cycle that goes through all vertices of the graph.
A graph is
hamiltonian
if it has a hamiltonian cycle.
A graph is
hypohamiltonian
if it has at least two vertices, and removing any one vertex of the graph leaves it hamiltonian.
A graph is
3-connected
if it has at least four vertices, and removing any two vertices from the graph still leaves it connected.
A graph is
planar
if it can be drawn on the plane without any two edges crossing.
A graph is
nonplanar
if it is not planar.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Moderator note:
Good observations. Finding counter examples in graph theory can be difficult, and the Petersen graph crops up often.
Only C is true.
A is false. A hypohamiltonian graph might not be hamiltonian. In fact, the common definition of hypohamiltonian graph is exactly that: graphs that are not hamiltonian, but becomes hamiltonian on removing any vertex. A simple example (also the smallest) is the Petersen graph .
B is also false. A hypohamiltonian graph can easily be planar; a simple example is K 4 , the complete graph on four vertices. It is planar: take a triangle and a point inside it, and join each pair of points. It is hypohamiltonian: removing any vertex leaves a triangle which is trivially hamiltonian.
C is true. Note that after removing any one vertex, the remaining graph is hamiltonian. Thus removing one more vertex will still leave the graph connected (take a hamiltonian cycle in the graph; this connects all vertices, and since it's a cycle, removing any one vertex still leaves a path that connects all vertices). Thus removing any two vertices still leaves the graph connected, so it is 3-connected.