2
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ Where is this proof from? $\endgroup$ – Michael McQuade Nov 15 '18 at 6:04
  • 2
    $\begingroup$ Text from MIT 6042. $\endgroup$ – shiva Nov 15 '18 at 6:34
2
$\begingroup$

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).

$\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.