Proof for a graph has Euler tour iff each vertex has even degree

7.8k Views Asked by At

This is the proof:

enter image description here enter image description here

I was able to understand this proof except the last part. They consider the edge $\{u, v_i\}$ to prove that if $W$ is not the Euler tour then it is not the longest walk as well, as it can be extended a new walk $W^{'}$ can be formed. However they state:

$W^{'}=u,v_i,v_{i+1},..., v_k, v_1, v_2,..., v_i $ and this contradicts our statement that each node has even degree, as in this case $v_i$ has odd degree. So isn't it wrong to consider it? (As $W^{'}$ is not even possible in our scenario of nodes with even degree)

1

There are 1 best solutions below

0
On BEST ANSWER

Notice that in order to have a contradiction, what we need to show is that there is no longer walk than $W$. So while making an assumption on $W'$, we just need to choose $W'$ such that length of $W'$ is more than $W$. We don't assume $W'$ is the longest walk.

In other words, there might be another shorter walk, say $v_i, a_1, a_2,...,a_m$ which makes degree of $v_i$ even but not the part of the proof since we are assuming there is a longer walk. In this case, longest walk might be $u,v_i,v_{i+1},..., v_k, v_1, v_2,..., v_i, a_1, a_2,...,a_m$ with $u = a_m$ (because we need to have a closed walk in order for it to be the longest). As long as we don't assume $W'$ is the longest walk but a longer walk, we may have odd degrees in it. That is the same reason why the proof had to state $v_k = v_0$ for $W$ (since we assumed it is the longest).