Question

a) Define a Hamilton circuit in a simple graph.

b) Give some properties of a simple graph that imply that it does not have a Hamilton circuit.

Short answer

• (a) A Hamilton circuit is a simple circuit in which each vertex of the graph is visited exactly once

• (b)A graph having a vertex of degree 1 cannot have a Hamilton circuit.
• A simple graph having a smaller circuit in it cannot have a Hamilton circuit.

Step-by-step solution

Step 1: Explanation of Hamilton circuit in a simple graph

• A Hamilton circuit is a simple circuit in which each vertex of the graph is visited exactly once
• A graph must not have a vertex of degree 1 to have a Hamilton circuit.
• For instance, figure 1 contains a Hamilton circuit and figure 2 does not have a Hamilton circuit because it has a vertex of degree 1.

Step 2: Explanation of some properties of a simple graph

• A Hamilton circuit starts and ends at the same vertex such that the vertex does not get repeated.
• If there is a vertex of degree 1, then there is only one vertex to reach that vertex. So, the vertex has to be repeated twice, which does not define a Hamilton circuit. As a result, a graph having a vertex of degree 1 cannot have a Hamilton circuit.
• A simple graph having a smaller circuit in it is not a Hamilton circuit.

• For instance, assume two figures as shown.

• Figures 1 contains a Hamilton circuit as the path does not repeat and it does not contain a vertex with degree 1 whereas, figure 2 does not contain a Hamilton circuit as its vertex has degree 1.