# How to prove all trees have at least as many leaves as its maximum degree?

EDIT:

I think I found the issue. $$m_h = n - (\Delta T + 1)$$, true. But the order of $$H$$ is not $$n$$, it's $$n_H = n-1$$. So $$m_H = n_h - \Delta T$$. Therefore, replacing all instances of $$\Delta T + 1 below this point with$$\Delta T\$ will result in the wanted solution.

Original post:

I want to show this:

Prove that if $$T$$ is a tree, then $$T$$ has at least $$\Delta(T)$$ leaves.

I read this similar question, but ended up with showing $$T$$ has at least $$\Delta(T)+1$$ leaves. While this technically proves the original statement, that leads me to wonder why then that the statement does not say:

Prove that if $$T$$ is a tree, then $$T$$ has at least $$\Delta(T)+1$$ leaves instead.

My attempt to prove the original proposition (number of leaves $$\geq\Delta(T)$$).

Proof. Let $$T$$ be an order $$n$$ tree with maximum degree $$\Delta(T)$$. The size of $$T$$ must be $$m=n-1$$ by definition of a tree. We want to show $$T$$ must have at least $$\Delta(T)$$ leaves.

Set $$v\in T$$ be some vertex with $$\deg(v)=\Delta(T)$$. Define $$H = T-v$$ be an induced subgraph of $$T$$ with $$v$$ removed. Then the size of $$H$$ must be \begin{align} m_H &= m - \Delta(T)\\ &= n - 1 - \Delta(T)\\ &= n - (\Delta(T) + 1) \end{align}

So $$H$$ is a forest of order $$n_H = n-1$$ with size $$m_H = n - (\Delta T + 1)$$. By definition of a forest, $$H$$ has $$k = \Delta(T) + 1$$ components.

Let $$k_1$$ be some component of $$H$$. If $$k_1$$ has only one vertex $$v_1$$, then $$v_1$$ was a neighbor of $$v$$ and a leaf of $$T$$ (because $$\deg_H(v_1)=0\implies \deg(v_1) = 0 + 1 = 1$$ before removing $$v$$). Let $$i$$ denote the number of such components.

Choose $$k_2$$ from the remaining $$k-i$$ components. $$k_2$$ must have 2 or more vertices (else it would follow under $$k_1$$'s rules). Because $$k_2$$ is connected and acyclic (as $$T$$ was an acyclic tree), $$k_2$$ is a tree. Therefore, $$k_2$$ has at least 2 leaves, only one of which could be a neighbor of $$v$$. Therefore, $$k_2$$ contains at least one leaf of $$T$$.

Thus, the components of $$H$$ each contribute at least one leaf to $$T$$.

So $$T$$ has at least $$k = \Delta T + 1$$ leaves.

$$\square$$

Where have I gone wrong?

See my edit above.

Proof. Let $$T$$ be an order $$n$$ tree with maximum degree $$\Delta(T)$$. The size of $$T$$ must be $$m=n-1$$ by definition of a tree. We want to show $$T$$ must have at least $$\Delta(T)$$ leaves.

Set $$v\in T$$ be some vertex with $$\deg(v)=\Delta(T)$$. Define $$H = T-v$$ be an induced subgraph of $$T$$ with $$v$$ removed. Then the size of $$H$$ must be \begin{align} m_H &= m - \Delta(T)\\ &= n - 1 - \Delta(T)\\ &= n - (\Delta(T) + 1) \end{align}

So $$H$$ is a forest of order $$n_H = n-1$$ with size $$m_H = n - (\Delta T + 1) = n_H - \Delta T$$. By definition of a forest, $$H$$ has $$k = \Delta(T)$$ components.

Let $$k_1$$ be some component of $$H$$. If $$k_1$$ has only one vertex $$v_1$$, then $$v_1$$ was a neighbor of $$v$$ and a leaf of $$T$$ (because $$\deg_H(v_1)=0\implies \deg(v_1) = 0 + 1 = 1$$ before removing $$v$$). Let $$i$$ denote the number of such components.

Choose $$k_2$$ from the remaining $$k-i$$ components. $$k_2$$ must have 2 or more vertices (else it would follow under $$k_1$$'s rules). Because $$k_2$$ is connected and acyclic (as $$T$$ was an acyclic tree), $$k_2$$ is a tree. Therefore, $$k_2$$ has at least 2 leaves, only one of which could be a neighbor of $$v$$. Therefore, $$k_2$$ contains at least one leaf of $$T$$.

Thus, the components of $$H$$ each contribute at least one leaf to $$T$$.

So $$T$$ has at least $$k = \Delta T$$ leaves.

$$\square$$