Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this 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$.

share|cite|improve this answer
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$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.