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.

×

Problem Loading...

Note Loading...

Set Loading...