Advertisements

**Hamilton path**: a path that passes through every vertex in a graph exactly once.

**Hamilton circuit**: a circuit that passes through every vertex in a graph exactly once (except for the vertex that is both the start and end, which is visited twice).

**Theorem 1:**A complete graph K

_{n}has a Hamilton circuit for n≥3.

**Theorem 2:**If G is a connected simple graph with n vertices, where n≥3, then G has a Hamilton circuit, if the degree of each vertex is at least n/2.

Using the
theorem, we can observe that there are 5 vertices, so n≥3;

Furthermore,
each vertex has at least deg(2): therefore, a Hamilton circuit may exist. One such circuit is: a, c, d, e, b, a

## 0 Comments