Connected Subgraph of Tree is Tree
Jump to navigation
Jump to search
Theorem
Let $T$ be a tree.
Let $S$ be a subgraph of $T$ such that $S$ is connected.
Then $S$ is also a tree.
Proof
Follows directly from the fact that by definition, $T$ has no circuits.
As $T$ has no circuits, then nor can $S$ have.
Hence $S$ is a connected simple graph with no circuits.
Thus by definition, $S$ is a tree.
$\blacksquare$