Subgraph of Tree

From ProofWiki
Jump to: navigation, 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$

Personal tools
Namespaces
Variants
Actions
Navigation
ProofWiki.org
ToDo
Toolbox
Google AdSense