Here we give definitions and links to several different types of tree structures

Simple Definitions:

  1. A tree (or free tree) is a connected, acyclic, undirected graph

  2. If an undirected graph is acyclic, but disconnected, it is called a forest.

  3. rooted trees have a distinguished node called the root - r.

  4. x is an ancestor of y if x is on the unique simple path between r and y.

  5. In the case above, y is a descendent of x.

  6. A node is both a descendent and a ancestor to itself.

  7. If x is an ancestor to y and x!=y then x is a proper acestor of y.

  8. Proper descendent is similarly defined.

The following are equivalent:

  1. G is a free tree.

  2. Any 2 vertices in G are connected by a unique SimplePath

  3. G is connected, but if any edge is removed from E, the resulting graph is disconnected
  4. G is connected, and |E|=|V|-1.
  5. G is acyclic, and |E|=|V|-1.
  6. G is acyclic, but if any edge is added to E, the resulting graph contains a cycle.