0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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$

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