# Number of duplicate cases in graphs - hamiltonian and nonhamiltonian paths

Suppose that we set the number of vertexes in a graph (and suppose that in a graph, there is no subgraph separate or isolated from other subgraphs).

Then, there are several ways to connect the vertexes using edges.

Out of those graphs possible, there will be some graphs which have hamiltonian paths (I am not talking of cycles) and graphs that do not have hamiltonian paths.

We know that some graphs can be redrawn without changing edge and vertex information into another graph. (e.g. rotation, reflection etc.)

So, if we count the number of total graphs possible that hamiltonian paths, how many of them will be virtually equal to each other? And how do you get the number?

Also, for graphs that do not have hamiltonian paths, how many of them will be virtually equal to each other? How do you get the number?

-

Jargon alert: What you call "virtually identical" graphs are commonly known as isomorphic graphs, so a rephrase of one of your questions might be

How many non-isomorphic graphs on $n$ vertices have Hamiltonian paths?

Now comes the bad news: there's no known general answer to that question. For a specific number of vertices, like 10, there are ways to get the answer, but they are incredibly time-consuming. Sorry 'bout that.

-

If you instead ask for the number of nonisomorphic Hamiltonian graphs (ie. graphs that contain a Hamiltonian cycle) then the sequence in context is the following

http://oeis.org/A003216

Perhaps someone could compute a few terms of the related sequence for graphs with Hamiltonian paths and put it on sloane?

-