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?


  • $\begingroup$ 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). $\endgroup$ – Mankind Feb 11 '15 at 17:07
  • 1
    $\begingroup$ 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. $\endgroup$ – Manuel Lafond Feb 11 '15 at 17:47
  • $\begingroup$ I've edited "there is an edge $e$" to "there exists an edge $e$" to make it more clear. $\endgroup$ – 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.

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

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.