2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ By B'(T) do you mean $\beta'(T)$, and is this the minimum size of an edge cover of $T$? By △T do you mean $\Delta(T)$, and is this the maximum degree of $T$? Are you assuming that $T$ is a tree? Especially in graph theory where a lot of notation is relatively new, you should define your terms before you use them. But in general, you shouldn't ask questions that require everyone to read your mind. $\endgroup$ – Misha Lavrov Dec 9 '18 at 16:06
  • $\begingroup$ Yes, B'(T) is the minimum size of edge coverage, $\triangle$ T is maximum degree of T. T is a tree $\endgroup$ – Mera Insan Dec 9 '18 at 16:07
0
$\begingroup$

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

House of Graphs: https://hog.grinvin.org/ViewGraphInfo.action?id=318

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.
$\endgroup$
0
$\begingroup$

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

$\endgroup$

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.