A graph is Hamilton-connected if, for any vertices

and

, there is a Hamiltonian path from

to

. In most cases the Harary graphs are circulants, or have a circulant as an edge subgraph (see [1] or [4] for the explicit construction). For example, if

is even or

is even, then

is a circulant graph. And if

is odd, then

has a circulant as an edge subgraph. When

, the circulants that arise are connected, not bipartite, and not a cycle, and therefore the Chen–Quimpo theorem [2] on Hamilton-connectedness of such circulants applies: such graphs are Hamilton-connected.

The case

is different, because the circulant graphs that underlie the Harary graphs are not all Hamilton-connected.

•

is a bipartite circulant and so is not Hamilton-connected, though it is Hamilton-laceable, by the Chen–Quimpo theorem.

•

can be proved to be not Hamilton-connected: there is no path from the unique vertex of maximum degree to the vertex two steps away in the natural circular order.

•

is the reason for this Demonstration, which shows the paths that arise in a proof that these graphs are Hamilton-connected. There are several different cases based on the parity of the starting vertex and the position of the target vertex.

[3] F. Harary, "The Maximum Connectivity of a Graph,"

*Proceedings of the National Academy of Science*,

**48**(7), 1962 pp. 1142–1146.

www.jstor.org/stable/71730.

[4] D. B. West,

*Introduction to Graph Theory*, 2nd ed., Upper Saddle River, NJ: Prentice-Hall, 2001 pp. 150–151.