I was wondering if you could help me prove the following.
$G$ is a tree $\iff$ deleting any edge will disconnect it.
And a similar one:
$G$ is a tree $\iff$ adding any edge will create a cycle.
I know we should use the fact that if $G$ is a tree, then $G-v$ is also a tree for $v$ such that $deg(v)=1$.
I also know that any tree has at least two vertices whose degree is 1.
Could you help me with this?
Thank you.
Best Answer
First claim is incorrect as stated. It should be
$G$ is a tree if and only if $G$ is connected and erasing any edge will disconnect it. (otherwise two disconnected trees are a counterexample for the converse)
$\Rightarrow$ is easy. $G$ is connected by the definition of the tree. Now assume by contradiction that erasing some edge $uv$ doesn't disconnect it. Then, there is a path $P$ between $u$ and $v$ in $G\backslash uv$, but then $P \cup \{ uv \}$ is a cycle in $G$ contradiction.
$\Leftarrow$: $G$ is connected. Assume now by contradiction that $G$ contains a cycle $C$. Then erasing some edge from the cycle doesn't disconect it, contradiction.
Second claim is also wrong.
$G$ is a tree if and only if $G$ has no cycles and adding any edge will create a cycle. (otherwise any connected graph satisfies the second condition)
$\Rightarrow$ $G$ has no cycles by the definition of the tree. Now, we prove that adding any new edge will create a cycle.
Let $uv$ be any edge not in $G$. Since $G$ is a tree, it is connected, and thus there is a path $P$ between $u$ and $v$. Then adding $uv$ creates the cycle $P \cup \{uv\}$.
$\Leftarrow$: $G$ has no cycle. We need to show that $G$ is connected.
Let $u,v$ be vertices in $G$. If $uv$ is an edge we are done, otherwise, adding $uv$ will create a cycle $C$ which of course contains $uv$ as an edge. Erasing now $uv$ from this cycle, we are left with a path connecting $u$ and $v$.