0
$\begingroup$

There is a question asked by portal about Tree having no vertex of degree 2 has more leaves than internal nodes

so we want to prove this claim by induction and an answer from Micheal Biro suggested to split the tree at an internal vertex. If the internal vertex has degree $k$, you get $k$ pieces, each with no internal vertex of degree 2.

So my question is "how did we know that each piece has no internal vertex of degree 2?"

What about trees like this tree for example: enter image description here

The vertex $u$ after removing one edge became an internal vertex with degree 2

PS: sorry could not put my question as a comment at the answer in the original question because I'm new and have not earned that privilege yet, and this question really got me thinking and I'm assuming that the answer is going to be really simple but I just can't see it

$\endgroup$
1
$\begingroup$

Remove the internal vertex, and one can certainly end up with components that have vertices of degree two. The trick is to remove the internal vertex, and then for each component add it back in separately. So you end up with essentially each component plus the internal vertex with the other components removed.

enter image description here

$\endgroup$
1
$\begingroup$

You should only split the tree at the designated vertex, not remove that vertex (and its adjacent edges). So your example splits into three trees having $2$, $4$, and $6$ vertices respectively.

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