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 Kn 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