2

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?

user252412
  • 23

3 Answers3

3

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$

dtldarek
  • 37,381
  • I got the proof but not how As all the entries in the sum above are non-negative, so we obtain... – Mahesha999 Feb 10 '15 at 17:20
  • @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. – dtldarek Feb 10 '15 at 17:27
2

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

paw88789
  • 40,402
1

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.

Hagen von Eitzen
  • 374,180