## Tracing a Hamiltonian Cycle on the 3-6 Graph on 18 Vertices

A few weeks ago I constructed a 3-6 graph on 18 vertices. My strategy then was to start with 3 sets of 6 vertices, two of which were already connected to form a Hamilton cycle of length 6. My object then was to interconnect the vertices to create a 3-6 graph, and I was able to do this successfully.

**Graph A**

My adviser then wanted me to rearrange the vertices to see if there existed a Hamiltonian graph of length 18 in the above 3-6 graph I had drawn. I was able to successfully rearrange the vertices to clearly illustrate that there was one (image below).

**Graph B**

He also asked me to write an algorithm so that starting at any vertex, I could trace the Hamilton cycle of length 18. The algorithm is included below.

**Algorithm:**

Name the following three groups of vertices in Graph A.

Outer Vertices {C, I, L, D, R, O}

Middle Vertices {F, H, K, N, Q, A}

Inner Vertices {B, G, J, E, P, M}

Choose any vertex in Graph A

You can start anywhere in the pattern and it loops until you have returned to your starting vertex. The following two rules must also be kept:

1) Visit each vertex once and only once

2) The first time you travel Middle-Middle or Outer-Outer sets the direction you will travel throughout the cycle (clockwise or counterclockwise). Once set, this direction must always be followed.

**Pattern:**

Outer

Inner

Middle

Middle

Inner

Outer

No trackbacks yet.