# Trees and leaf: Graph Theory

Let T be a tree with at least two vertices and let $v \in V(T)$. If T-v is a tree, then v is a leaf.

Attempt: Let T be a tree and let v be a leaf of T. Then T-v is a tree.
Let $a,b \in V(T-v)$. We must show that there is an (a,b) path in T-v. We know that since T is connected, there is (a,b)-path P in T. I claim that O does not include the vertex v. Since v is neither the first nor the last vertex on this path, it has two distinct neighbors on the path, contradicting the fact that $d(v)=1.$ Therefore P is an (a,b)-path in t-v and T-v is connected and a tree.

I just proved the converse of my original question. But a little stuck proving original question.

-

Do you know that a tree of $n$ vertices has $n-1$ edges?

If so, then suppose $T$ has $n$ vertices (and hence $n-1$ edges). Then $T-v$ has $n-1$ vertices and $n-1-\mathrm{deg}(v)$ edges. Hence, if $T-v$ is a tree, then $\mathrm{deg}(v)=1$.

-
Nice solution. If you change it just a bit you can prove "if and only if". – N. S. May 13 '13 at 17:14

Suppose $v$ is not a leaf, then we will show that $T-v$ is disconnected. Use induction; one can check that this is true if $|V(T)|=3$. Now suppose $|V(T)|=n$, then there exists a smaller subtree $T_1$ such that $|V(T_1)|<n$ and $T_1$ has $v$ as a non-leaf node. By induction hypothesis $T_1-v$ is disconnected and so is $T$.

-