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

From ProofWiki
Jump to navigation Jump to search


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

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


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.