2
$\begingroup$

Let $T$ be a tree in which the largest degree of a node equals to $t$. Let $n_1$ denote the number of nodes of degree $1$ in $G$. Prove that $n_1 ≥ t$

I understand why this works but I am not sure how to prove it mathematically. It makes sense, because vertices of degree one are those at the end of each leaf (let their number be n) and/or the vertex in the beginning of the tree that doesn't branch into more than one edge. And the vertex with highest degree is gonna have at max n edges connected to it. Am I making sense? any help in the formal proof?

$\endgroup$
3
$\begingroup$

Your inquality is certainly true for $n \leq 2$. For bigger trees, consider the following lemma:

$$\#\text{leaves} = 2 + \sum_{\deg(v)\; \geq\; 2}\Big(\deg(v)-2\Big).\tag{$\spadesuit$}$$

As all the entries in the sum above are non-negative, so we obtain

$$\#\text{leaves} \geq 2 + \max_{\deg(v)\; \geq\; 2}\Big(\deg(v)-2\Big) = \max_{v \in V} \deg(v)$$

which is exactly what we need.

Proof of the $\spadesuit$ equality:

We know that the sum of all degrees is twice the number of edges and the number of edges in any tree is the number of vertices minus one, so $$\sum_{v\in V}\deg(v) = 2m = 2(n-1).$$

Naturally $\sum_{v \in V}1 = n \cdot 1 = n$, hence

$$\sum_{v \in V}\Big(\deg(v)-2\Big)= -2.$$

Splitting $V$ into leaves and non-leaves we get

$$\sum_{\deg(v) = 1}\Big(\deg(v) - 2\Big) + \sum_{\deg(v) \geq 2}\Big(\deg(v) - 2\Big) + 2 = 0,$$

that is,

$$\sum_{\deg(v) = 1}\Big(-1\Big) + \sum_{\deg(v) \geq 2}\Big(\deg(v) - 2\Big) + 2 = 0,$$

simplifying

$$\sum_{\deg(v) \geq 2}\Big(\deg(v) - 2\Big) + 2 = \sum_{\deg(v) = 1}\Big(1\Big) = \#\text{leaves}.$$ $$\\\tag*{$\square$}$$

I hope this helps $\ddot\smile$

$\endgroup$
  • $\begingroup$ I got the proof but not how As all the entries in the sum above are non-negative, so we obtain... $\endgroup$ – Maha Feb 10 '15 at 17:20
  • $\begingroup$ @Mahesha999 First, we sum over $\deg(v) \geq 2$, so $\deg(v)-2 \geq 0$. Second, if the entries are non-negative, then the sum is bigger than or equal to its maximum summand. $\endgroup$ – dtldarek Feb 10 '15 at 17:27
2
$\begingroup$

Consider the tree to be rooted with the root being a vertex of maximum degree. Each edge from the root must lead to a different leaf (perhaps to more than one leaf).

$\endgroup$
1
$\begingroup$

Let $v$ have degree $t$ and neighbours $v_1,\ldots, v_t$. For each vertex $u\ne v$ let $\ell(u)$ denote the length of the (in a tree: uniqe) shortest path from $u$ to $v$, and let $\phi(u)\in\{v_1,\ldots,v_t\}$ be the last node before $v$ in this path. Let $S_i=\{\,u\ne v\mid \phi(u)=v_i\,\}$ for $1\le i\le t$. Then the $S_i$ are pairwise disjoint and nonempty (because $v_i\in S_i$). For each $i$, pick $u_i\in S_i$ with $\ell(u_i)=\max\{\,\ell(u)\mid u\in S_i\,\}$. Show that $u_i$ is a leaf.

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