Tree

Dependencies:

1. Path in Graph

There are 2 ways of defining a free tree (sometimes simply called tree):

• An undirected acyclic connected graph.
• An undirected graph where there is exactly one simple path between any two vertices.

In a tree, vertices of degree 1 are called leaves.

Proof of equivalence of definitions

Let $G$ be an undirected graph. We will prove the contrapositive, that if $G$ is cyclic or disconnected, then it is false that there is exactly one simple path between any 2 vertices.

If $G$ is disconnected, there are 2 vertices which are not connected. There are 0 paths between these vertices.

Let $G$ be cyclic. Let $u$ and $v$ be 2 vertices on a cycle in $G$. This means there are at least 2 simple paths from $u$ to $v$.

If there are 0 paths from $u$ to $v$, then $u$ and $v$ are disconnected, which means $G$ is disconnected.

Let there be multiple simple paths from $u$ to $v$. Let $p_1$ and $p_2$ be 2 such paths. Let $w_1$ and $w_2$ be the first and second vertices common to $p_1$ and $p_2$ when going from $u$ to $v$. Then $w_1$ and $w_2$ form a cycle. Therefore, $G$ is cyclic.

Dependency for:

1. Graphic matroid
2. Tree iff connected and deleting edge disconnects
3. Adding edge between 2 trees gives a tree
4. Tree iff acyclic and adding edge creates cycle
5. Deleting edge from tree gives 2 trees
6. The undirected version of a rooted tree is a free tree
7. G = (V, E) is a tree iff G is acyclic and |E| = |V|-1
8. Tree has at least 2 leaves
9. Spanning tree

Info:

• Depth: 2
• Number of transitive dependencies: 5

Transitive dependencies:

1. /sets-and-relations/equivalence-classes
2. /sets-and-relations/relation-composition-is-associative
3. /sets-and-relations/equivalence-relation
4. Graph
5. Path in Graph