Proving a rooted tree has a height given $n \in N$, $n \geq 2$

62 Views Asked by At

There are 4 statements that hold for $n \in N$ assuming $n \geq 2$

  1. Every rooted tree with $n$ vertices has height $\geq$ 2

  2. Every rooted tree with $n$ vertices has height $ \leq n$

  3. There exists a rooted tree with $n$ vertices with height equal to 2.

  4. There exists a rooted tree $G$ with $n$ vertices with height equal to $n$.

I only get statement 2 since from my understanding, the height of the tree is the longest path from a root node to a leaf, and I am not sure how all the other statements hold true, if they do how do you prove it?

  1. Let's say $n = 2$. Then the maximum height you can get is $1$ which is $\not \geq 2$

  2. This ties in with 1. that if $n=2$ the height is $1$ which is $1 \leq 2$

  3. If we let $n = 2$, there can't be a tree with height $=n=2$ because the max is $1$

  4. Same goes for this statement.