8.05 Hamiltonian networks and paths

State whether the following graphs contain a Hamiltonian path:

a

b

c

State whether the following graphs contain a Hamiltonian cycle:

a

b

c

d

e

f

g

State a Hamiltonian path for each of the following graphs:

a

b

c

Start the path at vertex A for the following graph:

List a Hamiltonian cycle, starting with vertex A, for each of the following graphs:

a

b

c

Determine whether each of the following graphs is Hamiltonian:

a

b

c

d

e

f

g

h

Determine whether each of the following graphs is semi-Hamiltonian:

a

b

c

d

e

f

g

h

Kate draws the mudmap below to represent all the houses she has to visit during her milk run:

Vertex	Residence
A	\text{Kate}
B	\text{Xanthe}
C	\text{Ursula}
D	\text{Lisa}
E	\text{Ellie}

Kate wants to plan a route that is time efficient by visiting each house only once, starting and finishing at her own residence. List a route that Kate could follow.

A mail man is planning his route in a certain area using the graph below:

Vertex	Residence
A	\text{William}
B	\text{Ivan}
C	\text{Vincent}
D	\text{Sean}
E	\text{Kenneth}
F	\text{Noah}

The mail man starts his route at William's residence. He wants his route to be time efficient by passing by each house only once. List the path the mailman should follow.