# Remove edge from tree, number of vertices

Prove that if $T$ is a tree on at least $k+1$ vertices and max degree at most $d$, then there exists an edge $e$ such that the removal of $e$ causes $T$ to split into two trees where at least one of them has between $k$ and $dk$ vertices.

Obviously I know that if $T$ has at most $dk+1$ vertices then removing an edge leading to a leaf gives what we need. But what if there are more vertices? Where does the max degree come into play?

Thanks.

• This looks weird to me, so I might be misunderstanding something. Say $T$ is on 4 vertices, so $k=3$. And if $d=2$, then you can have the linear tree x-x-x-x. If you remove the middle edge, you get two trees, where each has 2 vertices, which is not between $k$ and $dk$ (which is 3 and 6). – Mankind Feb 11 '15 at 17:07
• I think all it takes is for that edge to exist. In your example, remove an edge other than the middle one and you get one tree having 3 vertices. – Manuel Lafond Feb 11 '15 at 17:47
• I've edited "there is an edge $e$" to "there exists an edge $e$" to make it more clear. – ctlaltdefeat Feb 11 '15 at 17:50

Pick a vertex $r$ and set it as the root of $T$.

The subtree of $T$ rooted at a vertex $v \neq r$ is the tree induced by $v$ and all its descendants. Denote it by $T_v$ and its number of vertices by $|T_v|$.

Let $ch(r) = \{v_1, v_2, \ldots, v_h\}$ be the children of the root $r$. You can prove that one of the two following holds for any tree $T$ with at least $k + 1$ vertices and maximum degree $d$ :

1) for every $v_i \in ch(r)$, $|T_{v_i}| < k$

2) $T$ has a subtree having between $k$ and $dk$ vertices

which would prove the statement (if 1) holds, removing a leaf edge finds a desired tree, and if 2) holds, one can choose the edge parent to the root of the subtree found).

Suppose there is a tree $T$ for which both do not hold. Then let's assume that $T$ is a minimal counter-example (i.e. the statement is true for all rooted trees with at least $k + 1$ vertices, maximum degree at most $d$ and with strictly less vertices).

Since 1) does not hold, then there is some $v_i \in ch(r)$ such that $|T_{v_i}| \geq k$. If $|T_{v_i}| \leq dk$, then 2) holds. So assume $|T_{v_i}| > dk$.

Since $T$ is minimal and $T_{v_i}$ has at least $k + 1$ vertices and max degree at most $d$, 1) or 2) holds for $T_{v_i}$. If 1) holds, then $T_{v_i}$ has at most $d(k - 1) + 1 < dk$ vertices, contradicting the previous assumption.

So instead suppose that 2) holds. Then $T_{v_i}$ has a subtree having between $k$ and $dk$ vertices, and so does $T$, a contradiction.

• Let the tree be a root and $k$ leaves. Your argument breaks down because all of the induced subtrees have $1$ vertex. – ctlaltdefeat Feb 11 '15 at 20:51
• You're right - shame on me for handwaving that particular case. I have edited the answer with something that should work. – Manuel Lafond Feb 11 '15 at 22:14