• … that comes up often.
• … and has some nice properties.

• For example, the graph we had that modeled a maze was a tree, because there were no cycles in that maze:

• Most of the other graphs we have looked at are not trees:

Theorem: An undirected graph is a tree iff there is exactly one simple path between each pair of vertices.

Proof: If we have a graph \(T\) which is a tree, then it must be connected with no cycles. Since \(T\) is connected, there must be at least one simple path between each pair of vertices.

If there is more than one path between two vertices, then parts of those paths could be joined to form a cycle. Thus, there must be exactly one path.

Now suppose we have a graph \(G\) where there exactly one simple path between vertices. This graph is clearly connected.

If \(G\) contains a simple circuit, then there are two paths between any vertices on that circuit. Thus contradicts the assumption, so there can be no circuits, and \(G\) is a tree.∎

• Our map tree wasn't rooted, but could have been:.
• It would have made sense to designate the entrance (\(a\)) as the root.
• Then we would have had this:

• Rooted trees are usually drawn with the root at the top, and edges directed down.
• But can be drawn some other way if it makes sense.
• If it's obvious from the context, we can leave out the arrows, and just understand that all edges are oriented downwards.

• A parent of a vertex is the (unique) vertex that is adjacent and closer to the root.
• A child is a vertex that is adjacent and further away from the root.
• e.g. in the maze rooted tree, \(g\) is the parent of \(k\). Each of \(d\), \(k\), and \(j\) are children of \(g\).
• Every node in a rooted tree (except the root itself) has a unique parent.
• Nodes that are children, or children-of-children, or further down the tree are descendants.
• Similarly, nodes up from another are its ancestors. The root is an ancestor of everything (except itself) .
• Nodes at the bottom with no children are leaves.
• Nodes with children are internal vertices.
• e.g. in the maze tree, the ancestors of \(k\) are \(g,h,e,a\). The leaves are \(c,b,f,k,j,i\). The others are internal.

• Even though it's the same graph, it doesn't make as much sense if we draw it like this:

• Admittedly, the parent/child terminology is backwards if we draw the tree like this.
• But it's right for a tree of descendants of somebody:

• The empty board would be the root.
• To make it into an actual tree we would have had to:
  • Throw away the disconnected nodes and keep only ones that can be reached by real game play.
  • Let the nodes capture the state of the board as well as plays made to get there: separate the two XO_/_X_/___ nodes and all of the other cases.
• That would make more nodes, but maybe makes sense as a model of a game like that: we might care how we got to a particular state.
• We can model any turn-based game with a rooted tree like this.

• As we discussed above.

• We can have a look at some properties and learn about the above situations.

Theorem: A connected graph with \(n\) vertices has \(n-1\) edges if and only if it is a tree.

Proof: [Tree implies \(n-1\) edges] For \(n=1\), the tree is a single vertex, so there are zero edges.

For a tree with \(n+1\) vertices, we assume for induction that trees with \(n\) vertices have \(n-1\) edges. In a tree with \(n+1\) vertices let \(v\) be a leaf (degree one) vertex. By removing \(v\), we get a tree with \(n\) vertices and thus \(n-1\) edges. When we replace \(v\), we get \(n\) edges.

[\(n-1\) edges implies a tree] Consider a graph \(G\) that is connected with \(n\) vertices and \(n-1\) edges. Suppose for contradiction that \(G\) contains cycles.

Let \(u\) and \(v\) be adjacent vertices in that cycle. If we remove the edge \((u,v)\), then the graph is still connected. We can continue to remove edges from cycles until no cycles remain in the graph. This gives a graph with \(n\) vertices and \(n-1-k\) edges, with \(k\ge 1\).

The resulting graph is a tree since it is connected and contains no cycles. This contradicts the first part of this proof: a tree must have \(n-1\) edges, but this has fewer.∎

Lemma: If any edge is removed from a tree, the result is a disconnected graph.

Proof: Since there is only one path between pairs of vertices in a tree, removing an edge from \(u\) to \(v\) disconnects \(u\) and \(v\).∎

Corollary: A connected graph with \(n\) vertices must have at least \(n-1\) edges.

Proof: Immediate from the above lemma: if we have to add edges to make a tree, then something was discconnected before.∎

• Any fewer edges and it will be disconnected.
• But of course, graphs with \(n-1\) vertices can be disconnected.

• It's fairly common to want some limit like that.
• A tree where each vertex can have at most \(m\) children is called an m-ary tree.
• Our code implies a 3-ary tree (or ternary tree).
• Much more common: at most two children, or a binary tree.

• Also a common thing to want, particularly in a data structure.
• When the children have an order like this, we'll call it a ordered rooted tree.

• For an order binary tree, there are two children, usually called the left child and right child.
• In code:

  typedef struct node {
      struct node *leftchild;
      struct node *rightchild;
      char *data;
  } node;

• Or an example drawn as a graph:

• Here, \(b\) has \(d\) as its left child, and \(e\) as its right child.
• We don't necessarily demand that all children be present: \(c\) has a right child, but no left child.
• There will definitely be leaves: \(d,g,h,f\) here.
• In code that means some of our pointers/references will be null.

• These groups are called levels.
• The root is at level 0; its children are at level 1; their children are level 2;…
• In the above example, \(d,e,f\) are at level 2.

• e.g. the above tree has height 3; the maze example has height 5.
• That is, the height is the maximum level in a tree.

• These trees are balanced:

• The one on the right is balanced, binary, and full.
• These are not balanced:

Theorem: An \(m\)-ary tree with height \(h\) has at most \(m^h\) leaves.

Proof: We can show this by induction on \(h\). For \(h=0\), we have only the root (which is also a leaf) and thus \(1=m^0\) leaves.

For height \(h\), notice that the subtrees below the root are (at most) \(m\) trees of height \(h-1\). By the induction hypothesis they each have at most \(m^{h-1}\) leaves. In total, we have \(m\cdot m^{h-1}=m^{h}\) leaves.∎

Corollary: If we have an \(m\)-ary tree with \(l\) leaves, then it has height \(h\ge \lceil\log_m l\rceil\). If the tree is balanced, it has \(h =\lceil\log_m l\rceil\).

• That might get us some nice algorithms, if we let it.