# Hamiltonian paths in cubic graph

Prove, that in cubic graph, for given vertices $u$ and $v$, there are even number of Hamiltonian paths which connect $u$ and $v$.

I got a hint, that considering a "metagraph", where vertices are hamiltonian paths is good idea. However, I'm not sure how the edges should look like (probably some kind of similarity between hamiltonian paths). Any futher hints are welcome.

• – Listing Jan 8 '14 at 19:06

As Listing proposed above (I still can't comment on math.stackexchange), Hamiltonian Path Exchanges is almost full proof for my question. The last thing you need is, that you can safely remove edge $uv$, because none of Hamiltonian paths from $u$ to $v$ will use this edge. Then, if $v$ is starting point, and $u$ is an end, $deg_G(u) = 2$ (because we just removed one edge), so for each $p$ which starts in $v$ and ends in $u$, we have $deg(p) = 1$ (in $G'$). So each path have one neighbour, thus amount of them are even.