Graphs: trees, induction proof 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.
 A: 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$. 
A: Here’s one approach. First prove that a graph with no cycle either has no edges or has a vertex of degree $1$. Thus, a non-trivial tree has a vertex of degree $1$, i.e., a leaf. Use this observation to prove by induction that a graph with $n$ vertices is a tree iff it has exactly $n-1$ edges and is connected. Then observe that adding an edge to a tree cannot disconnect it, so it must create a cycle (since the resulting graph has too many edges to be a tree). Similarly, removing an edge cannot create a cycle, so it must destroy ‘tree-ness’ by disconnecting the graph.
A: Both of your statements follow from the fact that $G$ is a tree iff for any two vertices, there is exactly one simple path between them.  To see this, observe that it's true of one-vertex "empty" trees and preserved if you add or remove a leaf.
