Hamilton-Connected Harary Graphs

size of Harary graph

33

path start

3

path end

19

hide vertex labels

hide path

The Harary graphs

H

k,n

are a specifically defined family of graphs on

n

vertices that are

k

-connected and have the minimum possible number of edges for such a graph,

⌈1/2kn⌉

. A path is Hamiltonian if it visits all vertices without repetition. This Demonstration illustrates a proof that

H

3,n

, where

n

has the form

4r+1

, admits a Hamiltonian path from any vertex to any other. (The start vertex is green and end vertex is red.)