Tree | Sahithyan's Notes

A connected and acyclic graph. In this module, only undirected trees are discussed.

Any tree $T$ satisfies: $|E(T)| = |V(T)| - 1$ .

A graph where all of its connected components are trees. All acyclic graphs are forests. All subgraphs of a forest is also a forest.

If a forest has $m$ number of trees, it satisfies: $|E(T)| = |V(T)| - m$ .

A subgraph of a tree which is also a tree. Any connected subgraph of a tree is a subtree (as acyclicity is inherited).

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 (2nd statement is vacuous truth if not)
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: $(2) => (1)$

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

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

Assume the condition and $T$ is cyclic.
There exists a cycle of length $k$ edges and $k$ vertices
Case 1: $k=|V(T)|$ $k = ∣ V (T) ∣$
- $\implies |E(T)| \ge |V(T)|$
- Contradiction
Case 2: $k \lt |V(T)|$ $k < ∣ V (T) ∣$
- $|V(T)| - k$ vertices are outside the cycle
- They each require an edge to be connected to the graph ( $|V(T)| - k$ additional edges)
- Total number of edges becomes $|V(T)|$
- Contradiction

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

Assume the condition and $T$ is not connected.
Acyclic and not connected means it’s a forest which is a composition of trees (say $m$ ).
$|E(T)| = |V(T)| - 1$ is given which means $m = 1$ which means $T$ is connected (contradiction and proven)

A vertex with degree 1, in a tree.

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

Proof Hint

There is only 1 tree with 2 vertices. And it contains 2 leaves.
Suppose a tree $T$ has more than 2 vertices. And assume $T$ has 0 or 1 leaves.
Case 1: 0 leaves. Then all vertices have 0 or 2+ degree.
- Case 1.1: All vertices have 0 degree. Means disconnected graph. Contradiction.
- Case 1.2: All vertices have 2 or more degree. $\sum \text{deg}(v) = 2 |E(T)| = 2|V(T)| - 2 \ge 2|V(T)|$ . Contradiction.
Case 2: Only 1 leaf. All other vertices have 2+ degree (0 degree not possible). Then $\sum \text{deg}(v) = 2 |E(T)| = 2|V(T)| - 2 \ge 2 (|V(T)| - 1) + 1$ (2+ degree for $|V|-1$ vertices and $1$ degree for the leaf vertex). Contradiction.