Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question

2 Answers 2

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|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|improve this answer

Your Answer

 
discard

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.