Proof of a tree with a vertex of degree k and less than k vertices of degree 1

106 Views Asked by At

The question is : Does there exist a tree with a vertex of degree k and less than k vertices of degree 1?

I tried a lot but it is impossible to find. There is no tree with a vertex degree k and less than k vertices of degree 1.

But i don't know how can i prove it. :(

Can you prove it?

1

There are 1 best solutions below

0
On

HINT: Let $v$ be a vertex of degree $k$, and take $v$ as the root. Let $v_1,\ldots,v_k$ be the daughters of $v$. Show that the subtree rooted at $v_i$ must have at least one leaf for each $i\in\{1,\ldots,k\}$, and that these $k$ leaves must all be distinct.