Proof that G - v is a tree

Question

For school we have the following assignment:

Let v be a leaf of graph G. Prove that the following two statements are equivalent: (i) G is a tree, and (ii) G - v is a tree.

The first thing I came up with was this:

However, if you remove the leaf v in this tree you get the following:

This is not a tree anymore, right? Or am I being an idiot? Besides that the only thing related to this question that I could find on the internet was the following answer:

Suppose G is a tree with n vertices and n edges, then G - v has (n-1) vertices and (n-2) edges. Since G is acyclic G - v must also be a tree.

Besides the problem above, should this proof (is it actually a proof?) not say:

Suppose G is a tree with n vertices and n-1 edges, ...

Answer 1

You're exactly correct. Your verbage and wording might need a little finessing, but the ideas are correct.

A tree is defined to be a simple graph with $n$ vertices and $n-1$ edges. Equivocally, a tree is a connected, acyclic graph.

Suppose $T$ is a tree with $|V(T)| = n$. By definition of a tree, $|E(T)| = n - 1$. Let $v \in V(T)$ be a leaf. Consider $T - v$. By definition $|V(T - v)| = n - 1$. As $v$ is a leaf, removing $v$ from $T$ also removes a single edge, thus resulting in $n - 2$ edges. As $T - v$ has $|V(T - 1)| = |E(T - v)| + 1$, the definition of a tree is satisfied and so $T - v$ is a tree.

Alternatively, you could prove connectivity by contradiction and acyclicity directly. I think the proof counting the number of vertices and edges is simpler though.

Answer 2

In fact, the common answer of counting edges runs into a circular argument, since that statement is proven with your initial question as a lemma to prove it.

The definition of a tree is an acyclic connected graph.

Taking $v$ as a leaf, $G-v$ is clearly acyclic, and connectedness follows by noting for any $x, y$ in $V (G) \setminus {v}$ that the unique $xy$-path in $G$ is contained in $G − v$. Therefore, $G-v$ is a tree also. This is the method to answer your question.

---

For the counting argument:

To prove $G$ is a tree with $n$ vertices $\implies |E| = n-1$, we use induction.

$n=1$ is trivial as there are $0$ edges. Any tree has a leaf, so removing this gives us a tree $G-v$ with $n-1$ vertices. By induction, there are $n-2$ edges. Adding back the leaf and edge we reach our conclusion.