Connected Subgraph of Tree is Tree

From ProofWiki
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$