2
$\begingroup$

I'm attempting exercise 15 from the end of the first section in Diestel's Graph Theory. The exercise asks:

Show that any tree $T$ has at least $\Delta(T)$ leaves. $\Delta(T)$ denotes the maximum degree of any vertex in T. $d(v)$ denotes the degree of vertex $v$

I came up with the following:

$Proof.$ Let $T = (V, E)$ be a tree with an arbitrarily selected root, $r$. Let $L \subseteq V$ denote the set of vertices of degree 1 in T, i.e. the leaf vertices of $T$.

Now let $v \in V - L$ be an inner-vertex of $T$ (i.e. not a leaf), and let $d(v) = \Delta(T)$. As an inner-vertex of the tree, clearly $v$ must lie on some path $rTu$ for some $u \in L$, and as a result, $1$ of the $\Delta(T)$ incident edges of $v$ must lead to $u$. By the definition of a tree, each path from $r$ to a leaf $w \in L$ is uniquely defined. It follows that all $\Delta(T) - 1$ other edges incident to $v$ must belong to unique paths leading to other leaf nodes $w \neq u$, giving us at least $\Delta(T)$ leaves. $\Box$

I'm not convinced. Any suggestions?

$\endgroup$
3
$\begingroup$

I would structure the proof as follows. Consider an internal vertex $v$ with degree $\Delta(T)$; we would like to show that there are at least $\Delta(T)$ leaves that are descendants of $v$. Each child of $v$ is either a leaf or an internal vertex. Suppose there are $n_1$ children that are leaves and $n_2$ that are internal vertices. We have $n_1 + n_2 = \Delta(T)$.

Each child $c$ of $v$ that is an internal vertex will only have leaf descendants that are not descendants of any other child $c'$ of $v$. For if they did indeed have a common descendant $d$, there would be more than one path from $d$ to $v$. Thus there are at least $n_2$ such leaves, and consequently there are at least $n_1 + n_2 = \Delta(T)$ leaves.

$\endgroup$
  • $\begingroup$ Thanks for your response. I agree, your proof is far more explicit, and reads better. Just for clarification, was the general gist of my attempt correct? $\endgroup$ – swingballchamp42 Oct 3 '17 at 17:20
  • $\begingroup$ The gist of your attempt is correct (you are making use of the same uniqueness property that I mention). $\endgroup$ – Hans Hüttel Oct 3 '17 at 17:33
2
$\begingroup$

Now let $v\in V−L$ be an inner-vertex of $T$ (i.e. not a leaf), and let $d(v)=\Delta(T)$

When you say "let $v\in V-L$", it sounds like you are talking about an arbitrary vertex, and when you say "let $d(x)=\Delta(T)$", it sounds like you want $v$ to be a particular vertex, namely the one of largest degree. So you should replace the first quotation with "let $v$ be the vertex in $T$ with the largest degree".

It follows that all $Δ(T)−1$ other edges incident to vv must belong to unique paths leading to other leaf nodes $w≠u$.

I think this conclusion is where you are sweeping details under the rug...


Here's how I would structure the proof. You do not need to talk about the root of the tree at all.

Consider a vertex $v$ which achieves the maximum degree $\Delta(T$), and consider what happens when you remove $v$. Show that

  • the resulting graph has several connected components, each of which is a tree
  • the neighbors of $v$ are all in different components,
  • each component has two leaves (this is a standard theorem, every tree has at least two leaves)
  • at least one of the two leaves in each component corresponds to a leaf in the original graph $T$.
$\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.