Burton Rosenberg
1 April 2003
A Graph G is a set V of vertices and a set E of edges, each edge connecting two distinct vertices. Graphs are drawn with the vertices as dots and the edges as lines connecting the dots.
A path in a graph is a collection of edges leading in an unbroken sequence from a start vertex to an end vertex. If edges are named by the vertex endpoints (v_x,v_y), then a path would be something like:
(v_1,v_2), (v_2, v_3), ... (v_{k-1},v_k)
A cycle is a path which begins and ends on the same vertex.
A path or a cycle is simple if it does not intersect itself,
that is, any vertex appears at most once on the path.
A Hamiltonian cycle is a simple cycle in the graph which passes through all vertices. Some graphs have them, and others do not. It is in fact a difficult problem, given a graph, to decide whether the graph has a Hamiltonian cycle or not.