enter image description here

The above graph has the following properties :

  • $1$) Every vertex is start vertex of some hamiltonian path.
  • $2$) It contains no hamiltonian cycle.
  • $3$) It has no cycle of length $3$.
  • $4$) It is planar.
  • $5$) It has at least $3$ vertices.

Property $5$ is only listed to avoid the $K_2$

I conjecture that this is the smallest graph with these properties.

The smallest graph fulfilling $1$) and $2$) and $5$) seems to have $9$ nodes, if $3$) also is required, then $10$ nodes seems to be the minimum. The example with $9$ nodes, which is introduced in the question Is there a name for graphs with the following property, is planar.

Is this the smallest graph with the properties $1-5$ ?


Yes, it is.

I verified this by checking all graphs with properties 2, 3, and 4 (planar triangle-free non-hamiltonian graphs) to see if they have property 1 (being homogeneously traceable). As I mentioned in my answer to the linked question, there are no non-hamiltonian homogeneously traceable graphs with 3 to 8 vertices, so we only need to check graphs with 9, 10, or 11 vertices.

A straightforward way to check in Sage if a graph $G$ is homogeneously traceable is:

all(len(G.longest_path(v)) == len(G) for v in G.vertices())

It seems to be faster on average to first compute the automorphism group, and find the longest path for one vertex in each orbit, instead of checking each vertex, as in this function:

def homtrac_orbits(g):
    orbits = g.automorphism_group(return_group=False, orbits=True)
    n = len(g)
    return all(len(g.longest_path(o[0])) == n for o in orbits)

You can use Sage to generate all planar triangle-free non-hamiltonian graphs on a given number of vertices, and check if any are homogeneously traceable. This runs in a short time for up to 10 vertices, and in several hours on my machine for 11 vertices, and finds none.

def ptfnh(G):
    """Graph property: planar, triangle-free, non-hamiltonian.

    If G has the property, then any subgraph obtained by deleting one edge also has it,
    so this may be used with the Sage graphs generator.
    return G.is_planar() and G.is_triangle_free() and not G.is_hamiltonian()

for n in range(5, 12):
    totct = 0
    for G in graphs(n, ptfnh):
        if not G.is_connected():
        totct += 1
        if homtrac_orbits(G):
            print G.to_dictionary()
    print n, ':', totct, 'planar connected triangle-free non-hamiltonian graphs'


5 : 5 planar connected triangle-free non-hamiltonian graphs
6 : 15 planar connected triangle-free non-hamiltonian graphs
7 : 51 planar connected triangle-free non-hamiltonian graphs
8 : 210 planar connected triangle-free non-hamiltonian graphs
9 : 1006 planar connected triangle-free non-hamiltonian graphs
10 : 5831 planar connected triangle-free non-hamiltonian graphs
11 : 39210 planar connected triangle-free non-hamiltonian graphs

However, this approach is too slow for 12 vertices, if we want to see what examples show up there. It is much faster to generate all the planar triangle-free non-hamiltonian graphs using the nauty gtools. A command ./geng -c -t 12 | ./planarg | ./hamheuristic generates all 300416 connected triangle-free planar non-hamiltonian graphs on 12 vertices in about 20 seconds on my machine.

As the command hamheuristic suggests, it is a heuristic approach, so some hamiltonian graphs may be passed through if a hamiltonian cycle was not discovered. It only omits graphs where it actually finds a hamiltonian cycle.

Passing the output of this to Sage, to check for homogeneous traceability with homtrac_orbits, finds only a single example with 12 vertices, which it shows thus: enter image description here

This is isomorphic to your example.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.