Let $T$ be a tree. $G$ is a new graph by adding vertix $x$ and connect it to one vertex through an edge in $T$.

Question

Let $T$ be a tree. $G$ is a new graph by adding vertix $x$ and connect it to one vertex through an edge in $T$.

I have to prove that $G$ is a tree

I know that adding one vertix does not make a circle in the tree, but I don't know how to show that ...

Thanks!

Answer 1

Let $x$ be the new vertex and $y\in T$ the vertex you connect it to.

• $G$ is connected: If $a,b$ are distinct vertices of $G$, then either both are alread in $T$, hence connected by a path, or one of them (say, $a$) is the new vertex $x$. Then a path from $y$ to $b$, prepended with the new edge $xy$ gives us a path from $a$ to $b$

• $G$ has no cycles. Indeed, assume $v_0v_1\ldots v_n$ (with $v_n=v_0$) is a cycle. If none of the $v_i$ is $x$, this is a cycle in $T$, which does not exist. If one of the $v_i$ equals $x$, then $v_{i-1}=v_{i+1}=y$ (with the usual convention about $v_{-1}$ and $v_{n+1}$), but going back and forth along the same edge is not allowed in a cycle.

Answer 2

An other solution is a simple corollary of an equivalent definition of Tree:

A graph $G$ is a tree if and only if it is connected and has $n-1$ edges, where $n$ is the number of vertexes in $G$