Connected Graph is Tree iff Removal of One Edge makes it Disconnected/Sufficient Condition/Proof 1
Jump to navigation
Jump to search
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
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$.
$\blacksquare$