# Connected Graph is Tree iff Removal of One Edge makes it Disconnected/Sufficient Condition

## Theorem

Let $G = \struct {V, E}$ be a tree.

Then for all edges $e$ of $G$, the edge deletion $G \setminus \set e$ is disconnected.

## Proof 1

Let $G$ be a tree.

Then by definition $G$ has no circuits.

From Condition for Edge to be Bridge, every edge of $G$ is a bridge.

Thus by definition of bridge, removing any edge of $G$ will disconnect $G$.

## Proof 2

Let $G$ be a tree.

Hence *a fortiori* $G$ has no cycles.

Let $v, v' \in V$.

Let the edge $\set {v, v'}$ be removed.

Aiming for a contradiction, suppose $G$ is still connected.

Then *a priori* $v$ and $v'$ are connected.

By If Vertices are Connected then Path Exists between them, there is a path $\tuple {v, v_1, \ldots, v'}$ of length $2$ or more.

Hence $\tuple {v, v_1, \ldots, v', v}$ is a cycle in $G$.

This contradicts the statement that $G$ has no cycles.

The result follows by Proof by Contradiction.