Discrete Mathematics An Open Introduction, 4th Edition

One very useful and common approach to studying graph theory is to restrict your focus to graphs of a particular kind. For example, you could try to really understand just complete graphs or just bipartite graphs, instead of trying to understand all graphs in general. That is what we are going to do now, looking at trees. Hopefully by the end of this section we will have a better understanding of this class of graph, and also understand why it is important enough to warrant its own section.

Does the definition above agree with your intuition for what graphs we should call trees? Try thinking of examples of trees, and make sure they satisfy the definition. One thing to keep in mind is that while the trees we study in graph theory are related to trees you might see in other subjects, the correspondence is not exact. For instance, in anthropology, you might study family trees, like the one below,

So far so good, but while your grandparents are (probably) not blood relatives, if we go back far enough, it is likely that they did have some common ancestor. If you trace the tree back from you to that common ancestor, then down through your other grandparent, you would have a cycle, and thus the graph would not be a tree.

You might also have seen something called a decision tree (such as the algorithm for deciding whether a series converges or diverges). Sometimes these too contain cycles, as the decision for one node might lead you back to a previous step.

Both the examples of trees above also have another feature worth mentioning: There is a clear order to the vertices in the tree. The definition of a tree does not include this added structure, although we can impose such a structure by considering rooted trees, where we simply designate one vertex as the root. We will consider such trees in more detail later in this section.

In this section, we will explore some basic properties of trees, which will serve as an excellent introduction to writing proofs about graphs. We will also consider a special kind of tree, called a spanning tree, which is a tree that includes all the vertices of a connected graph. Finally, we will briefly consider rooted trees.

We wish to really understand trees. This means we should discover properties of trees: what makes them special and what is special about them.

A tree is a connected graph with no cycles. Is there anything else we can say? It would be nice to have other equivalent conditions for a graph to be a tree. That is, we would like to know whether there are any graph theoretic properties that all trees have, and perhaps even that only trees have.

To get a feel for the sorts of things we can say, we will consider three propositions about trees. These will also illustrate important proof techniques that apply to graphs in general, and happen to be a little easier for trees.

Our first proposition gives an alternate definition for a tree. That is, it gives necessary and sufficient conditions for a graph to be a tree.

Read the proof above very carefully. Notice that both directions had two parts: the existence of paths, and the uniqueness of paths (which related to the fact that there were no cycles). In this case, these two parts were really separate. In fact, if we just considered graphs with no cycles (a forest), then we could still do the parts of the proof that explore the uniqueness of paths between vertices, even if there might not exist paths between vertices.

This observation allows us to state the following corollary.

⁵

A corollary is another sort of provable statement, like a proposition or theorem, but one that follows direction from another already established statement, or its proof.

We do not give a proof of the corollary (it is, after all, supposed to follow directly from the proposition), but for practice, you are asked to give a careful proof in the exercises. When you do so, try to use proof by contrapositive instead of proof by contradiction.

Our second proposition tells us that all trees have leaves: vertices of degree one.

The proposition is quite useful when proving statements about trees, because we often prove statements about trees by induction. This is a proof technique that we investigate fully in Section 4.5, but for now, all we need to understand is that it is useful to compare a given tree to smaller trees. To show something is true of a tree with $v$ vertices, we will assume the thing is true of all trees with $v-1$ vertices. By removing a vertex of degree 1, we get this smaller tree, and then we just need to show that putting the vertex back doesn’t mess us up.

Is there a tree with exactly 7 vertices and 7 edges? Try to draw one. Could a tree with 7 vertices have only 5 edges? There is a good reason that these seem impossible to draw.

We will prove that this proposition is true for all possible values of $v\ge 1\text{.}$ Note that if $v=1\text{,}$ then the tree must have $0$ edges, so yes, $e=v-1\text{.}$ We could then look at trees with $v=2$ vertices (there is only one, and it has $e=1=v-1$ edges) and then all trees with $v=3$ vertices, and then $v=4\text{,}$ and so on, but that would take forever. Literally!

Instead, we will do a version of proof by contradiction called the minimal criminal. We will assume the proposition is not true (just like we would start any proof by contradiction). This means that there is some smallest tree for which it isn’t true. If this smallest counterexample (i.e., minimal criminal) has $v$ vertices, then we are guaranteed that all trees with $v-1$ vertices are not counterexamples. Let’s see how this works out.

One of the advantages of trees is that they give us a few simple ways to travel through the vertices. If a connected graph is not a tree, then we can still use these traversal algorithms if we identify a subgraph that is a tree.

First we should consider if this even makes sense. Given any connected graph $G\text{,}$ will there always be a subgraph that is a tree? Well, that is actually too easy: You could just take a single vertex of $G\text{.}$ If we want to use this subgraph to tell us how to visit all vertices, then we want our subgraph to include all of the vertices. We call such a tree a spanning tree.

It turns out that every connected graph has one (and usually many).

How do we know? We can give an algorithm for finding a spanning tree! Start with a connected graph $G\text{.}$ If there is no cycle, then $G$ is already a tree and we are done. If there is a cycle, let $e$ be any edge in that cycle and consider the new graph $G_1=G-e$ (i.e., the graph you get by deleting $e$). This tree is still connected: Since $e$ belonged to a cycle, there were at least two paths between its incident vertices. Now repeat: If $G_1$ has no cycles, we are done; otherwise define $G_2$ to be $G_1-e_1\text{,}$ where $e_1$ is an edge in a cycle in $G_1\text{.}$ Keep going. This process must eventually stop, since there are only a finite number of edges to remove. The result will be a tree, and since we never removed any vertex, a spanning tree.

This is by no means the only algorithm for finding a spanning tree. You could have started with the empty graph and added edges that belong to $G\text{,}$ as long as adding them would not create a cycle. You have some choices as to which edges you add first: You could always add an edge adjacent to edges you have already added (after the first one, of course), or add them using some other order. Which spanning tree you end up with depends on these choices.

Although we will not consider this in detail, these algorithms are usually applied to weighted graphs. Here every edge has some weight or cost assigned to it. The goal is to find a spanning tree that has the smallest possible combined weight. Such a tree is called a minimum spanning tree. Finding the minimum spanning tree uses basically the same algorithms as we described above, but when picking an edge to add, you always pick the smallest (or when removing an edge, you always remove the largest).

⁶

If you add the smallest edge adjacent to edges you have already added, you are doing Prim’s algorithm. If you add the smallest edge in the entire graph, you are following Kruskal’s algorithm.

So far, we have thought of trees only as a particular kind of graph. However, it is often useful to add additional structure to trees to help solve problems. Data is often structured like a tree. This book, for example, has a tree structure: Draw a vertex for the book itself. Then draw vertices for each chapter, connected to the book vertex. Under each chapter, draw a vertex for each section, connecting it to the chapter it belongs to. The graph will not have any cycles; it will be a tree, but a tree with a clear hierarchy which is not present if we don’t identify the “book vertex” as the “top”.

As soon as one vertex of a tree is designated as the root, then every other vertex on the tree can be characterized by its position relative to the root. This works because there is a unique path between any two vertices in a tree. So from any vertex, we can travel back to the root in exactly one way. This also allows us to describe how distinct vertices in a rooted tree are related.

If two vertices are adjacent, then we say one of them is the parent of the other, which is called the child of the parent. Of the two, the parent is the vertex that is closer to the root. Thus the root of a tree is a parent, but is not the child of any vertex (and is unique in this respect: All non-root vertices have exactly one parent).

Not surprisingly, the child of a child of a vertex is called the grandchild of the vertex (and it is the grandparent). More generally, we say that a vertex $v$ is a descendent of a vertex $u$ provided $u$ is a vertex on the path from $v$ to the root. Then we would call $u$ an ancestor of $v\text{.}$

For most trees (in fact, all except paths with one end the root), there will be pairs of vertices neither of which is a descendant of the other. We might call these cousins or siblings. In fact, vertices $u$ and $v$ are called siblings provided they have the same parent. Note that siblings are never adjacent (do you see why?).

All of this flowery language helps us describe how to navigate through a tree. Traversing a tree, visiting each vertex in some order, is a key step in many algorithms. Even if the tree is not rooted, we can always form a rooted tree by picking any vertex as the root. Here is an example of why doing so can be helpful.

The key to how we partitioned the tree in the example was to know which vertex to assign to a set next. We chose to visit all vertices in the same generation before any vertices of the next generation. This is usually called a breadth-first search (we say “search” because you often traverse a tree looking for vertices with certain properties).

In contrast, we could also have partitioned the tree in a different order. Start with the root; put it in $A\text{.}$ Then look for one child of the root to put in $B\text{.}$ Then find a child of that vertex, into $A\text{,}$ and then find its child, into $B\text{,}$ and so on. When you get to a vertex with no children, retreat to its parent, and see if the parent has any other children. So we travel as far from the root as fast as possible, then backtrack until we can move forward again. This is called depth-first search.

These algorithmic explanations can serve as a proof that every tree is bipartite, although care needs to be spent to prove that the algorithms are correct. Another approach to prove that all trees are bipartite, using induction, is requested in the exercises.