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}$.


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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.