The minimum edge cover of a tree is at least the maximum degree

Question

Let $T$ be a tree with maximum degree $\Delta(T)$, and let $\beta'(T)$ denote the size of the minimum edge cover of $T$. The question is to prove that $\beta'(T) \ge \Delta(T)$.

I started by proving that each tree has at least $\Delta(T)$ using induction on $n$. Then I tried using the fact that if we take the edge connected to each leaf then we will have minimum edge coverage equal to $\Delta(T)$ in case all the leaves are connected to the vertex of max degree, if not, then we need at least one more edge. Does it make sense?

Answer 1

In the case where there is only one vertex of maximum degree in $T$, and it's adjacent to all other vertices, you are right that $\beta'(T) = \Delta(T)$, and we can prove this by looking at the edges that cover each of the other vertices.

In other cases, you claim that we need at least one more edge. First of all, this is not always true: we could have a tree that looks like

and this is still possible to cover with $5$ edges. Whether true or false, it needs more proof. You are probably thinking something like "if we take the edge cover we were using previously, which consisted of all the edges incident to the maximum-degree vertex, then that doesn't work anymore and it needs one more edge". But that doesn't mean there's not some more clever strategy, which doesn't start with that edge cover to begin with.

There are two strategies that you could pursue:

• The tree $T$ has $\Delta(T)$ branches stemming off of a vertex of maximum degree. You could argue that each of these branches needs at least one edge to cover it, and that no edge can cover two branches. It follows that any edge cover needs at least $\Delta(T)$ edges.
• You could prove that $T$ has at least $\Delta(T)$ leaves. Each leaf can only be covered by one edge, and these are all distinct, so this gives $\Delta(T)$ edges that must be in the edge cover no matter what.

Answer 2

Let $v$ be a vertex of a maximal degree $\Delta$ of the tree $T$. Let $N(v)$ be a set of neighbors of the vertex $v$. If any edge of $T$ is incident to at least two vertices $v,w$ of $N(v)$ then $u-v-w-u$ is a cycle, which cannot occur in a tree. So each edge cover need at least $|N(v)|=\Delta$ distinct vertices to cover $N(v)$.