Problem
An Euler tour of a graph is a closed walk that includes every edge exactly once.
(a) Show that if a digraph has an Euler tour, then the in-degree of each vertex equals its out-degree.
Definition: A digraph is weakly connected if there is a "path" between any two vertices that may follow edges backwards or forwards.
Suppose a graph is weakly connected. We will show that the graph has an Euler tour.
Definition: A trail is a walk in which each edge occurs at most once.
(b) Suppose that a trail in a weakly connected graph does not include every edge. Explain why there must be an edge not on the trail that starts or ends at a vertex on the trail.
In the remaining parts, assume that the graph is weakly connected, and the in-degree of every vertex equals its out-degree. Let $w$ be the longest trail in the graph.
(c) Show that if $w$ is closed, then it must be an Euler tour.
(d) Explain why all the edges starting at the end of $w$ must be on $w$.
(e) Show that if $w$ was not closed, then the in-degree of the end would be bigger than its out-degree.
(f) Conclude that if the in-degree of every vertex equals its out-degree in a finite, weakly connected digraph, then the digraph has an Euler tour.
Solution attempt
(a) Let $G$ be a digraph that has an Euler tour, and let $v$ be a vertex in $V(G)$ (the set of vertices of $G$).
Since the tour includes every edge exactly once, then it must include each edge into and out of $v$ exactly once. Also, whenever the tour goes through an edge $a$ into $v$, it must immediately go through an edge out of $v$. So, every edge $a$ that ends in $v$ must have a matching edge $b$ that starts at $v$ such that $a$ and $b$ appear in sequence in the tour. This means that there can't be more edges that end in $v$ than edges that start in $v$, and vice-versa.
Therefore, for every vertex $v$, $\textrm{indeg}(v)$ = $\textrm{outdeg}(v)$.
(b) Suppose that a trail in a weakly connected graph $G$ does not include every edge.
Let $e$ be an edge not included in the trail. This edge connects two vertices. By cases:
-
One of the vertices of $e$ is on the trail. Then, we are done.
-
No vertices of $e$ are on the trail. Let $v$ be any vertex of $e$. Since $G$ is weakly connected, then, by the provided definition, there is a "path" $p$ connecting $v$ to some vertex that is on the trail. Follow the "path" $p$, following its edges either backwards or forwards as needed, until it reaches a vertex $w$ that is on the trail. The last edge before the "path" reaches $w$ is an edge that either begins or ends in $w$, which concludes this case.
(c) Assume that $G$ is a weakly connected graph, $w$ is the longest trail in the graph, and $w$ is closed.
By contradiction, assume that $w$ is not an Euler tour. Then, $w$ doesn't include every edge.
By part (b), this means that there must be an edge $e$ not on $w$ that starts or ends at a vertex $v$ on $w$. By cases:
-
$e$ starts at $v$: following the closed walk $w$ by starting at $v$ and ending at $v$, and then following the edge $e$, produces a trail that is longer than $w$, which is a contradiction.
-
$e$ ends at $v$: following $e$ into $v$, and then following $w$ (by starting at $v$ and ending at $v$), produces a trail that is longer than $w$, which is a contradiction.
Therefore, $w$ must be an Euler tour.
(d) Let $v$ be the vertex at the end of $w$. By contradiction, assume there is an edge $e$ starting at $v$ that is not on $w$. Then, following $w$, and then $e$, produces a trail that is longer than $w$, which is a contradiction.
(e) Assume that $w$ is not closed. Let $v$ be the vertex at the end of $w$. Then, there are no edges starting at $v$, because, if there were any edges starting at $v$, then, from (d), these edges would be on $w$, contradicting the fact that $v$ is at the end of $w$. Therefore, $\textrm{outdeg}(v) = 0 < \textrm{indeg}(v)$.
(f) Let $w$ be the longest trail in a finite, weakly connected digraph $G$. Let $v$ be the vertex in the end of $w$. By (e), if $\textrm{indeg}(v) \leq \textrm{outdeg}(v)$, then $w$ is closed. So, since $\textrm{indeg}(v) = \textrm{outdeg}(v)$, then $w$ is closed. Since $w$ is closed, then, by (c), it must be an Euler tour.
Please, could someone verify this solution attempt? Thank you.
Best Answer
You are using "let" in two incompatible ways. In some places such as (a) "let $G$ be a digraph ... let $v$ be a vertex ...", you use it for universal quantification. But in other places such as (f) "let $w$ be the longest trail ... it must be an Euler tour", you use it for existential instantiation. It would be much better if you made a proper distinction between the two as I have described in this post.
Apart from that, your reasoning seems to be okay, except for one tiny issue:
(a) You wrote "every edge $a$ that ends in $v$ must have a matching edge $b$ that starts at $v$ such that $a$ and $b$ appear in sequence in the tour". That is true, but as written it only yields the conclusion that there are at least as many out-edges from $v$ as in-edges to $v$. Of course, you know how to fix this. Alternatively, simply note that the number of in-edge to $v$ is equal to the number of edges in the tour that end at $v$, which is equal to the number of edges in the tour that starts at $v$, and hence...