Graphs: trees, induction proof

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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$.