Trees

#matematik-discmath

Definition: Tree

A graph is a tree if it is Connected, and there are no Cycles in .

Theorem

Let be a tree with at least two vertices. Then

  1. For every pair of vertices there is a unique path in from to .
  2. The graph obtained from by removing any edge has two components, each of which is a tree.
  3. .

Proof:

  1. Take any . Since is connected, there exists a path from to . Now suppose is a different path from to . Then since and there exists such that for every but and , meaning is a cycle, contradicting that is a tree. Hence the path is unique.
  2. Removing any edge creates two components: each of which consisting of the nodes whose paths to each other did not contain the removed edge. Clearly these are connected and no cycles can be introduced, so they are both trees.
  3. Follows from (b); we induce on the number of edges. The base case is trivial. Now given , remove any edge, resulting in components and , each having strictly less vertices than . By our induction hypothesis, and , meaning