A multigraph $G$ has even no of Hamiltonian paths

discrete mathematicsgraph theoryhamiltonian-pathhamiltonicity

Following Corollary is taken from : HAMILTONIAN CYCLES AND UNIQUELY EDGE COLOURABLE GRAPHS

Definition (Stick) : A path $s= e_1,…,e_m$ in $G$,where the end vertices of the edge $e_i$ are $v_i$ and $v_{i+1}$ and $1\leq i \leq m$. The path s is called a stick.

Corollary : Let $G$ be a multigraph, let $u,v \in V$, and suppose that $d(w)$ is odd for each vertex $w\in$ $V$– {$u,v$} $\ne \phi$. Then number of Hamiltonian Paths in $G$ from $u$ to $v$ is even.

Proof : We may assume that $u$ and $v$ are adjacent vertices (if they are not we may add an edge between them); let $e$ be an edge between $u$ and $v$. We choose the stick $s$ to be the edge $e$ with $u=u_1$ and $v=v_2$; if $w \in V$ then $\epsilon(w)$ is the number of edges from $u$ to $w$.Consequently a Hamiltonian path $h$ beginning with $s$ and ending in $w$ gives rise to exactly $\epsilon( w )$ hamiltonian paths from $u$ to $v$. But by Theorem 1.1 the number of such paths ending in the set $W$={$w \in V$ : $\epsilon ( w )$ is odd} is even.

My understanding of proof :

  • Since the graph is Hamiltonian if the edge $uv$ is missing we add it.
  • Now that stick $s$ has to be the edge with $u=v_1$ does this mean
    $u=v_1$ is incident with last edge of stick.
  • For Hamiltonian paths to be to be even it is obvious that after
    deletion of {$u,v$} we are left with vertices of odd degree and since
    its a multigraph loops are allowed which leads to set $W$ being have
    paths of odd length i.e $\epsilon(w)$ is odd so we have even number
    of vertices and sum of odd degrees with even no of vertices is even.

But what I dont get from the proof is how there are $\epsilon(w)$ Hamiltonian paths?

Also I would like to know if I am going about the proof in right way, this is messing with head so I would like to know if I am wrong.

Best Answer

The proof says

A Hamiltonian path $h$ beginning with $s$ and ending in $w$ gives rise to exactly $\varepsilon(w)$ Hamiltonian paths from $u$ to $v$.

The way it gives rise to such paths is as follows: from $u$, take any of the $\varepsilon(w)$ edges to $w$, and then follow $h$ in reverse until you get to $v$.

This is invertible, up to the choice of edge between $u$ and $w$: given a Hamiltonian path $h'$ from $u$ to $v$ whose second vertex is $w$, start from the stick $s$ (getting us to $v$), then follow $h'$ in reverse until you get to $w$.

Formally, this is a bijection between $$ S_1 = \{(e', h) : e' \text{ is a $uw$ edge, $h$ is a $u-w$ Hamiltonian path starting with $s$}\} $$ and $$ S_2 = \{ h' : h' \text{ is a $u-v$ Hamiltonian path starting with some edge $e'$ from $u$ to $w$}\}. $$ For each $w$, either $\varepsilon(w)$ is even, or (by Theorem 1.1) the number of choices of $h$ is even. To get $|S_1|$, we multiply $\varepsilon(w)$ by the number of choices of $h$. Therefore $|S_1|$ is always even, and by the bijection $|S_2|$ is always even.

Sum over all $w$, and we get the total number of $u-v$ Hamiltonian paths. Since it's a sum of many even numbers, it must be even.

Related Question