Graphs, Trees

Trees

A tree is a connected graph with no cycles.

Exactly one path connects any two points in a tree. There must be at least one path, or the tree wouldn't be connected. Suppose there are two paths v and w that connect the same two points. Let i be the smallest index for which vi does not equal wi. Continue along both paths concurrently, watching for any repeated point. In other words, the smallest j and k, j≥i and k≥i, where vj = wk. Such a situation must occur eventually, since both paths end at the same point. This creates a cycle, and since a tree has no cycles, there is only one path.

The converse is also true. Every cycle implies two different paths connecting v1 to vN, hence single path graphs are acyclic.

Acyclic graphs are called forests (many trees). A connected forest is a tree.

If a tree contains v vertices, it contains v-1 edges. This is true for v=1, and can be proved by induction. Split the tree at any edge, dividing it into two smaller components. These subgraphs are disjoint, since the deleted edge was the only connecting path. Since both subtrees follow the formula vertices = edges + 1, so does the original tree.