Let T be an n-vertex tree with exactly 2k odd-degree vertices. Prove that T decomposes into k paths (i.e. its edge-set is the disjoint union of k paths).
My process so far: For every vertex, you need two neighbors if you are an internal vertex of a path, and one if you are the end vertex of a path. This means a vertex that has an odd degree should be the end vertex of a path. Each path has 2 end vertices, so 2k / 2 = k decompositions will occur.
Do you think this is a formal proof? Do I lack something in my thinking?
Best Answer
The other have pointed out the incompleteness of your proof. Let me show you how to find the actual paths.
Actually, let's show it more generally for forests (which consist of one or more disjoint trees). This makes it easiert to use induction w.r.t. the number of odd-degree vertices.
Induction start: ($2k=0$)
In general, if a tree has more than one vertex, then it has at least two leaves (this must be proven, but I assume you can do this), and every leaf is of odd degree (of degree one to be precise). Hence, a forest with no odd-degree vertices can only consist of isolated vertices (one-vertex-trees). Assuming a suitable definition of "decompose", we can argue that a graph without edges can be decomposed into $k=0$ paths.
Induction step: ($2k\to 2k-2$)
Let's say the forest $F$ has $2k>0$ odd-degree vertices. There must be a tree $T\subseteq F$ in the forest which has more than one vertex. This tree has at least two leaves, say $a,b\in T$. Let $P$ be the path in $T$ that connects $a$ and $b$. Construct $F'$ from $F$ by removing the edges of $P$ from $F$. Now, in $F'$ the vertices $a$ and $b$ are isolated (because they were of degree one in $T$). So, these are no longer of odd degree. The other vertices of $P$ lost two edges each, i.e. the parity of their degree has not changed. Thus, $F'$ has exactly two odd-degree vertices fewer than $F$, i.e. $2k-2$ many. So by induction hypothesis it decomposes into $k-1$ paths, and together with $P$ we have the $k$ decomposing paths of $F$.
$\square$