According to wolfram, $n$-wheel graphs have $4(n-1)(n-2)$ Hamilton paths in them.
$n$-wheel graph = http://mathworld.wolfram.com/WheelGraph.html http://mathworld.wolfram.com/HamiltonianPath.html here it states that n-wheel graphs have $4(n-1)(n-2)$ Hamilton paths in them.
Does anyone know a good explanation or proof to this statement? I cant seem to understand how they reached this number .
Thanks!
On
We can exhaust all the paths. Maybe there's a more elegant way, but here goes.
Let $(v_1, v_2, \ldots, v_{n - 1})$ an ordering of the $n - 1$ vertices outside the wheel. That is, $v_iv_{i+1}$ is an edge, modulo $n - 1$. It helps to draw a wheel and label the vertices in a clockwise fashion. Call the center of the wheel $c$.
Let's look at the paths in which $v_1$ is the start and some $v_j$ is the end. If $j = 2$, the Hamiltonian path has to travel the wheel cycle backwards, visiting $c$ after some vertex $v_k$ and coming back on the cycle at $v_{k - 1}$. So the path is of the form $v_1v_{n - 1}v_{n-2} \ldots v_kcv_{k-1} \ldots v_3v_2$. Now, $v_k$ can be any vertex but $v_2$, so there are $n - 2$ such paths.
If $j = n - 1$, the same argument applies, but we travel the cycle forward. So there are also $n- 1$ such paths.
If $j$ is another value, then the "clockwise" path travels to $v_{j - 1}$, then $c$, then $v_{n - 1}$ and then counterclockwise to $v_j$. The only other path does the same but in the reverse order (go to $v_{j - 1}$, $c$, $v_2$ and $v_j$). So that's two of them. Now, $j$ can take up to $n - 4$ values, so that's $2(n - 4)$ such paths.
And finally, if the path starts at $v_1$ and ends at $c$, there are two such paths - those that travel the wheel cycle in the two directions.
In total, there are $2(n - 1) + 2(n - 4) + 2 = 4n -10$ paths that start at $v_1$. In total that's $(4n - 10)(n - 1)$ paths that start at a vertex on a wheel.
If the path starts at $c$ and ends at say $v_1$, then there are two such paths. So $2(n - 1)$ paths start at $c$.
That's it ! We have them all. The grand total of paths is $(4n - 10)(n - 1) + 2(n - 1) = (4n - 8)(n - 1) = 4(n - 2)(n - 1)$.
The Mathworld link counts the number of directed Hamiltonian paths. I will count the number of undirected paths, which can each be oriented in two ways. Let the spokes of $W_n$ be the edges incident with the vertex of degree $n-1$ (the hub). Let the rim vertices be the vertices different from the hub.
First count the number of Hamiltonian paths having exactly 1 spoke. There are $n-1$ spokes, and each spoke corresponds to 2 Hamiltonian paths (counterclockwise & clockwise). So there are $2(n-1)$ such paths.
Now consider the number of Hamiltonian paths having 2 spokes. Consider two cases: 1) the rim vertices incident with the spokes are adjacent 2) the rim vertices incident with the spokes are not adjacent. In Case 1, there are $n-1$ ways to choose the spokes, and once the spokes are chosen, the start and end vertices of the path can be chosen in $n-2$ ways, for $(n-1)(n-2)$ paths. In Case 2, there are $\left(\binom{n-1}{2} - (n-1)\right) = \frac{(n-1)(n-4)}{2}$ ways to choose the spokes, and each choice of spokes corresponds to 2 Hamiltonian paths (counterclockwise & clockwise), for $(n-1)(n-4)$ paths.
Thus the total number of undirected Hamiltonian paths is:
$$2(n-1) + (n-1)(n-2) + (n-1)(n-4) = 2(n-1)(n-2)$$