Note: if you cannot remember the concepts of walks, paths and cycles, revise notes for 2.1 Introduction to Walks.

### Hamiltonian Paths

- A
**Hamiltonian path**is a path which visits every vertex of a graph exactly**once**. - Hamiltonian paths are useful for situations when every vertex
**must**be visited but the route taken does not necessarily matter. For example, when a message must be sent to every individual in a communication network. - There are no convenient methods (within the scope of Further Maths) for determining if a Hamiltonian path exists in a network and it must be determined through observation.

Example

A company has 6 distribution centres, named centre A-F. A delivery driver must deliver the company’s product to each centre. To optimise time, the driver plots a Hamiltonian path between the centres: B-A-D-C-E-F, as shown below: