I am a little bit confused by the proof of Theorem 1.8.1 (Euler 1736) on the page 23 of the textbook Graph Theory by Diestel.
Theorem 1.8.1 (Euler 1736)
A connected graph is Eulerian if and only if every vertex has even degree.
The porof can be found on page 23 Chapter 1.
Proof: The degree condition is clearly necessary: a vertex appearing k times in an Euler tour must have degree $2k$.
Conversely. let $G$ be a connected graph with all degrees even , and let
$W =v_0e_0…e_{l-1}v_l$
be a longest walk in $G$ using no edge more than once. Since $W$ cannot be extended, it already contains all the edges at $v_l$. By, assumption the number of such edges is even
Q:Why it actually should be even, where we made such an assumption.
Hence $v_l=v_0$ (why?)
Q:Here author asks why it is actually true, it is true because we made an assumption about even degree (I have some difficulties to show it for a general case, but let's assume all vertices have degree 2, than it's apparently the circle and $v_l$=$v_0$). Will appreciate example and explanation for a general case.
so $W$ is a closed walk.Suppose $W$ is not an Euler tour. Then $G$ has an end $e$ outside $W$ but incident with a vertex of $W$, say $e=uv_i$. Then the walk $uev_ie_i…e_{l-1}v_le_0…e_{i-1}v_i$ is longer than $W$, a contradiction.
Q:The main question is here, it's a contradiction to the definition of $W$, how it is connected to the Theorem. I don't see a connection between this contradiction and even degree of graphs.
I would appreciate if someone could elaborate a little bit according to the questions.
Best Answer
For your first question, the number of edges at $v_\ell$ is even because we assumed that every vertex of $G$ has even degree.
For your second question, suppose that $v_0\ne v_\ell$. Consider the edges that are in $W$ and meet $v_\ell$. One of them is $e_{\ell-1}$; if there are any others, there must be at least one $k<\ell$ such that $v_k=v_\ell$. Let $A=\{k:0<k<\ell\text{ and }v_k=v_\ell\}$. Note that if $k\in A$, then $k-1,k+1\notin A$, because $G$ has no loops. And if $k\in A$, then the edges $e_{k-1}$ and $e_k$ both meet $v_k=v_\ell$, so each $k$ in $A$ contributes two edges to the list of edges in $W$ that meet $v_\ell$. None of these edges is $e_{\ell-1}$, because $v_{\ell-1}\notin A$. Thus, $W$ has $2|A|+1$ edges that meet $v_\ell$; this is an odd number, which we already know is impossible. Thus, we must have $v_0=v_\ell$. (Now the edge $e_{\ell-1}$ gets paired up with the edge $e_0$.)
For your third question, the contradiction arose from the assumption that $W$ was not an Euler tour. Therefore $W$ is an Euler tour, and the result that we were trying to prove is established:
From this question and your first one I think that you may have lost sight of what was being proved here. Diestel had already shown that if $G$ has an Euler tour, then every vertex has even degree. Now he’s proving the converse.