Hamilton-Connected Harary Graphs

The Harary graphs are a specifically defined family of graphs on vertices that are -connected and have the minimum possible number of edges for such a graph, . A path is Hamiltonian if it visits all vertices without repetition. This Demonstration illustrates a proof that , where has the form , admits a Hamiltonian path from any vertex to any other. (The start vertex is green and end vertex is red.)


  • [Snapshot]
  • [Snapshot]
  • [Snapshot]


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.
[1] O. Baudon, J. Bensmail, E. Sopena, "Partitioning Harary Graphs into Connected Subgraphs Containing Prescribed Vertices," preprint. hal.inria.fr/docs/00/68/99/34/PDF/bbs2012.pdf.
[2] C. C. Chen and N. F. Quimpo, "On Strongly Hamiltonian Abelian Group Graphs," Lecture Notes in Mathematics, Vol. 884, (K. L. McAvaney, ed.), Berlin: Springer-Verlag, 1981 pp. 23–34. link.springer.com/chapter/10.1007%2 FBFb0091805.
[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.
    • Share:

Embed Interactive Demonstration New!

Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details »

Files require Wolfram CDF Player or Mathematica.