Proof completion: Determine a simple expression for $\tau(G)$ in terms of the vertex degrees of $G$. (details inside)

Question

I need some help completing a proof I wrote (or seeing a simpler solution to the same problem).

For a list of paths $P_1, \ldots , P_m$, let $L(P_1, \ldots, P_m)$ be the number of paths in $P_1, \ldots, P_m$ which are not closed. Let $\tau(G)$ be the smallest value of $L(P_1, \ldots, P_m)$ over all the lists pf paths $P_1,\ldots, P_m$ such that their edge sets partition $E(G)$ (i.e. each edge of $G$ appears in exactly one path). For example, if $G$ is a cycle with an extra edge, then $\tau(G) = 1$. Determine a simple expression for $\tau(G)$ in terms of the vertex degrees of $G$.

Let $A = \{v \in V(G): \operatorname{deg}(v)$ is odd $\}$. We first prove that $\tau(G) \leq \frac{|A|}{2}$.

Let $v \in A$. Start a path from $v$ and continue adding edges till it is not possible to add more edges to the path. Each time the path passes through a vertex $x$, it reduces the degree of $x$ by $2$. The path cannot terminate at a vertex of even degree, by the preceding fact. So, the path terminates at some $v' \in A$. Since $v$ has an odd degree, $v' \neq v$.

Now, consider the graph $G^{(1)} - \{e \in E(G): e$ is an edge in the preceding path $\}$. Let $A^{(1)}$ be the set of all vertices in $G^{(1)}$ with odd degree. It can easily be seen that $A^{(1)}=A-\{v, v'\}$. Continue the procedure till $A^{(n)} = \varnothing$. Then, the only vertices remaining are those with even degree, and the remaining edges can be partitioned into closed paths. Here, $L(P_1, \ldots, P_m) = \frac{|A|}{2}$.

Now, it remains to prove that it cannot be the case that $\tau(G) < \frac{|A|}{2}$.

Answer 1

You've actually done the "hard" direction already. To see that $\tau(G) \ge |A|/2$, first convince yourself that it's sufficient to show the following:

In any graph formed by the edge-disjoint union of a finite set of paths $P_1, \ldots, P_m$ (of which exactly $k$ are unclosed), there are at most $2k$ vertices of odd degree.

This is a pretty straightforward induction on $k$.