Connected Graph is Tree iff Removal of One Edge makes it Disconnected/Necessary Condition
Jump to navigation
Jump to search
Theorem
Let $G = \struct {V, E}$ be a connected simple graph such that:
- for all edges $e$ of $G$, the edge deletion $G \setminus \set e$ is disconnected.
Then $G$ is a tree.
Proof
Let $G$ be a connected simple graph such that for all edges $e$ of $G$, the edge deletion $G \setminus \set e$ is disconnected.
Hence, by definition, every edge of $G$ must be a bridge.
So by Condition for Edge to be Bridge, $G$ has no circuits.
Hence $G$ is a tree by definition.
$\blacksquare$