Proof by induction on a rooted tree with even number of vertices

Question

Let $T = (V, E)$ be a rooted tree with an even number of vertices. Prove by induction that there exists a set of edges $S \subseteq E$ such that every $v \in V$ is incident with an odd number of edges in $S$.

I was wondering if my argument is sufficient to prove the statement above:

Base case: $|V|=2$, there is only 1 edge and both vertices are incident with 1 edge $->$ $S \subseteq E$.

Inductive step:

Let $|V|>2$, implying that $T$ has at least 2 external vertices. Let us choose two arbitrary external vertices $w,u \in V$. Such vertices are only incident to 1 edge each, $e_w$ and $e_u$. We can say that $e_w,e_u \in S$.

By induction, there exists a set $S$ in $T'=T-\{w,u\}=(V',E')$ such that every $v \in V'$ is incident with an odd number of edges in $S$ because removing 2 vertices from a tree with an even number of vertices maintains the property $|V|=2n$.

Answer 1

As noted in the comments, your proof doesn't work.

The null graph on $0$ vertices clearly satisfies the condition. For some $n\in\mathbb N$, assume the condition holds for all rooted trees with $2n$ vertices, and let $T$ be a rooted tree with $2n+2$ vertices. We may choose $v$ to be a leaf of $T$ of maximal depth, and take $u$ to be its parent. Either one of three conditions may occur:

• if $d(u)=1$, then the graph has only two vertices and one edge. Then $S=\{uv\}$ satisfies the conditions of the problem.
• if $d(u)=2$, then $T-\{u,v\}$ is a rooted tree with $2n$ vertices. By the induction hypothesis, we may choose an edge set $S'$ that meets the conditions of $T-\{u,v\}$. Thus $S=S'\cup\{uv\}$ meets the conditions on $T$.
• if $d(u)>2$, then $u$ has children other than $v$. Since $v$ was chosen to have maximal depth, these children must all be leaves as well. Choose $v'$ to be one of them. $T-\{v,v'\}$ is a rooted tree with $2n$ vertices, so by the induction mypothesis we may choose an edge set $S'$ that meets the conditions of $T'-\{v,v'\}$. Now, consider $S=S'\cup\{uv,uv'\}$. $v$ and $v'$ clearly have are incident on one edge from $S$, $u$ is incident on two more edges from $S$ than it was from $S'$, which must be odd, and any remaining vertices in $T$ are incident on an odd number of edges as well. Therefore $S$ meets the criteria.

Since each of these three possibilities cover all the possible cases and each supplies an edge graph such that each vertex is incident on an odd number of edges, our proof is complete.

Answer 2

Here is a proof without explicit use of induction, which might be interesting to read.

---

Choose any vertex $r$ as root. This gives every edge a unique order, which points to $r$.

Now imagine that there is a boy sitting on every vertex. The boy sitting on the root $r$ is named $R$.

We say that boy $A$ "points to" boy $B$, if there is an edge connecting them, and the edge from $A$ to $B$ is in the direction pointing to $r$. It's clear that every boy points to another boy, except $R$, who doesn't point to anyone.

Also imagine that every boy, except $R$, holds a ball at beginning.

Now the boys start to pass the balls. For every boy different from $R$, if all the boys pointing to him have passed their balls, then he passes all the balls in his hand to the boy that he points to.

In other words, the procedure starts from those who sit on leaf vertices, since nobody points to them; and after a boy received all the balls from further boys, he passes all the balls to the one he points to.

In the end, all the balls are passed to $R$. We then define a set $S$ of edges: an edge is in $S$ if and only if the number of balls that have been passed through this edge is odd.

---

Let us verify that the set $S$ has the required property.

If boy $A$ points to boy $B$, then we write $c(AB)$ for the number of balls passed from $A$ to $B$. Thus we have $c(AB) \equiv 1_{AB \in S} \pmod 2$.

For every boy $B$ different from $R$, if $A_1, \dotsc, A_s$ are the boys pointing to him and $C$ is the boy he points to, then the number of edges in $S$ that $B$ is incident with is: $$1_{BC \in S} + \sum_{i = 1}^s 1_{A_iB\in S}\equiv c(BC)+\sum_{i = 1}^s c(A_iB) = 2c(BC) - 1 \equiv 1\pmod 2$$ Here we used the fact that $c(BC) = 1+\sum_{i = 1}^sc(A_iB)$, because $B$ passes all the ball he receives, plus the original ball he has.

It only remains to show that the number of edges in $S$ that $R$ is incident with is odd.

If $A_1, \dotsc, A_s$ are the boys pointing to $R$, then we have $\sum_{i = 1}^s 1_{A_iR\in S} \equiv \sum_{i = 1}^s c(A_iR)\pmod 2$. But the latter sum is simply the total number of balls, which is the number of vertices minus one, hence is odd.

---

The same argument shows that if the tree has an odd number of vertices and $r$ is any fixed vertex, then there is a set $S$ of edges such that all vertices are incident with an odd number of edges in $S$, except $r$, who is incident with an even number of edges in $S$.