Counting Hamiltonian cycles in a graph

combinatoricsdiscrete mathematicsgraph theoryhamiltonian-pathproof-verification

Given a graph $G = (W \cup U, E)$ where $W = \{w_1, w_2, …, w_n\}$, $U = \{u_1, u_2, …, u_n\}$ and $E = \{\{w_i, u_j\}: 1 \leq i, j \leq n\}$. The task is to calculate the number of Hamiltonian cycles in the graph G.

The way I tried solving was,

Our vertex set $V = \{w_1, w_2 … w_n, u_1, u_2, … u_n\}$

Since we know 2 vertices $w_i \in W \text{ and } u_j \in U$ are adjacent if $1 \leq i, u \leq n$, this makes every vertex in W adjacent to every vertex in U giving us a bipartite graph. Also by Dirac's theorem
$deg(v) \leq \frac{|V|}{2}$ for a graph to be Hamiltonian.

So the task at hand condenses down to finding the number of hamiltonian cycles in a complete bipartite graph with n and n vertices i.e. $K_{n,n}$. Which is $\frac{n!(n-1)!}{2}$, taken from here.

Is this the right way to solve this problem or am i missing something?

Best Answer

Since we know 2 vertices $w_i \in W \text{ and } u_j \in U$ are adjacent if $1 \leq i, u \leq n$, this makes every vertex in W adjacent to every vertex in U giving us a bipartite graph.

The correct statement here would be:

Since every edge is between a vertex in $W$ and a vertex in $U$, we have a bipartite graph. (The line I quoted from your proof doesn't say anything about edges in $W \times W$ or $U \times U$. Their non-existence is the crucial point).
Since the edge set is the full Cartesian product $W \times U$, we have a complete bipartite graph.

So the task at hand condenses down to finding the number of hamiltonian cycles in a complete bipartite graph with n and n vertices i.e. $K_{n,n}$.

Correct.

Which is $\frac{n!(n-1)!}{2}$, taken from here.

Yes, but the main point of the exercise is probably to show why that's the correct result.

Related Solutions

[Math] Can a bipartite graph have many Hamiltonian paths but no Hamiltonian cycle

Yes! The Georges graph has this property. This graph is the smallest known counterexample to the Tutte conjecture that any 3-connected bipartite 3-regular graph is Hamiltonian. It has 50 vertices and 75 edges.

I verified that every vertex is the initial vertex of a Hamiltonian path with some Sage code:

def homtrac_orbits(g):
    orbits = g.automorphism_group(return_group=False, orbits=True)
    return all(g.hamiltonian_path(o[0]) is not None for o in orbits)

def report(G):
    print G.name() + ':', homtrac_orbits(G), G.is_hamiltonian(), G.is_bipartite()

report(Graph(">>graph6<<qO`a`_WO?O?_?_?OO???K?@O?B_?@??__?_I?A?_?_????@?A?@???\
O????g???`????C????????A?????O????C??????????K?????K?????S?????K?????\
B????OO?????__??????C??????C??????A?????C????????D_??????I???????[\
??????AG??????GA_", name="Georges"))

You can see it on SageCell but it takes some time to run. It prints "Georges: True False True" when complete.

The Ellingham-Horton graphs on 54 and 78 vertices are also homogeneously traceable but non-Hamiltonian. The 54-graph can be checked with

report(graphs.EllinghamHorton54Graph())

(included in the above SageCell). I also checked the 78-graph but this is too slow to include in the SageCell.

It seems reasonable to guess that the other known counterexamples to Tutte's conjecture—namely the Owens graph, the Horton 92-graph, and the Horton graph—are also homogeneously traceable, but checking in Sage is too slow for those to verify that way.

[Math] Graph that joins an odd vertex with an even vertex

Proof: Since every edge in $G$ joins an odd vertex with an even vertex, it cannot be the case that two odd/even vertices are adjacent. Hence, $G$ is an $X,Y$-bigraph such that $X$ is the set of even vertices, and $Y$ is the set of odd vertices.

We wish to show that $|E(G)|$ is even. Suppose, on the contrary, that $|E(G)|$ is odd. Thus, there are an odd number of edges that are incident to vertices in $X$. This is a contradiction, as each vertex in $X$ is even.

Therefore, if $G$ is a graph such that every edge connects an even and odd vertex, then $G$ is bipartite, and $|E(G)|$ is even.

Best Answer

Related Solutions

[Math] Can a bipartite graph have many Hamiltonian paths but no Hamiltonian cycle

[Math] Graph that joins an odd vertex with an even vertex

Related Question