Tree | Sahithyan's Notes

A graph is a tree iff it’s connected and acyclic.

A graph is a forest iff it’s all connected components are trees. All acyclic graphs are forests. All subgraphs of a forest is also a forest.

Subgraphs of a tree is a

If a subgraph of a tree is also a tree, it’s a subtree.

Theorem

All 4 below statements are equivalent:

Proof Hint

First prove: $(1) => (2)$

A tree is connected (and acyclic) and assume it has more than 1 vertex
A connected graph implies any 2 vertices are connected by a path
Assume there are 2 distinct paths between 2 vertices, which means there is a cycle and it’s a contradiction

Then prove: $(1) => (3)$

Then prove: $(3) => (4)$

Then prove: $(4) => (1)$

Then prove: $(1) => |E(T)| = |V(T)|-1$

A vertex with degree 1, in a tree.

Any tree with 2 or more vertices, contains at least 2 leaves.