Prove that a finite, weakly connected digraph has an Euler tour iff, for every vertex, outdegree equals indegree 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.
 A: 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...
