1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

Just for anyone who will enter this question later:

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.

$\endgroup$

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.