Theorem of Eulerian Path
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.
$\endgroup$2 Answers
$\begingroup$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:
if every vertex of $G$ has even degree, then $G$ has an Euler tour.
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.
$\endgroup$ $\begingroup$Question 1: We are referring to the number of edges containing $v_l$. This is precisely the degree of $v_l$, which we have assumed to be even.
Question 2: To see $v_l = v_0$, note the number of times each vertex is entered or exited is even, with the possible exception of $v_0$ and $v_l$. Since all edges including $v_l$ have been traversed, we see the initial edge must have exited $v_l$, i.e. $v_l = v_0$.
Question 3: We have assumed $W$ to be a maximal length path that does not contain every edge. By showing there is a longer path, we arrive at a contradiction. Thus every maximal length path must contain every edge, and thus is an Eulerian circuit. Since everything is finite, we can show such a path must exist. We used the even degrees assumption to show $v_l = v_0$, which allowed us to construct a longer path.
$\endgroup$
