Trees

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.

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.

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

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.

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

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\), 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\). 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\). 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\), where \(e_1\) is an edge in a cycle in \(G_1\). 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\), 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.

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

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\).

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.

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

After completing this section, you should be able to:

1. Describe and identify trees.
2. Determine a spanning tree for a connected graph.
3. Find the minimum spanning tree for a weighted graph.
4. Solve application problems involving trees.

Whether we are talking about a family tree or a tree in a forest, none of the branches ever loops back around and rejoins the trunk. This means that a tree has no cyclic subgraphs, or is acyclic. A tree also has only one component. So, a tree is a connected acyclic graph. Here are some graphs that have the same characteristic. Each of the graphs in is a tree.

Let’s practice determining whether a graph is a tree. To do this, check if a graph is connected and has no cycles.

Mathematicians have had a lot of fun naming graphs that are trees or that contain trees. For example, the graph in is not a tree, but it contains two components, one containing vertices a through d, and the other containing vertices e through g, each of which would be a tree on its own. This type of structure is called a forest. There are also interesting names for trees with certain characteristics.

• A path graph or linear graph is a tree graph that has exactly two vertices of degree 1 such that the only other vertices form a single path between them, which means that it can be drawn as a straight line.
• A star tree is a tree that has exactly one vertex of degree greater than 1 called a root, and all other vertices are adjacent to it.
• A starlike tree is a tree that has a single root and several paths attached to it.
• A caterpillar tree is a tree that has a central path that can have vertices of any degree, with each vertex not on the central path being adjacent to a vertex on the central path and having a degree of one.
• A lobster tree is a tree that has a central path that can have vertices of any degree, with paths consisting of either one or two edges attached to the central path.

Examples of each of these types of structures are given in .

As we study trees, it is helpful to be familiar with some of their characteristics. For example, if you add an edge to a tree graph between any two existing vertices, you will create a cycle, and the resulting graph is no longer a tree. Some examples are shown in . Adding edge bj to Graph T creates cycle (b, c, i, j). Adding edge rt to Graph P creates cycle (r, s, t). Adding edge tv to Graph S creates cycle (t, u, v).

It is also true that removing an edge from a tree graph will increase the number of components and the graph will no longer be connected. In fact, you can see in that removing one or more edges can create a forest. Removing edge qr from Graph P creates a graph with two components, one with vertices o, p and q, and the other with vertices r, s, and t. Removing edge uw from Graph S creates two components, one with just vertex w and the other with the rest of the vertices. When two edges were removed from Graph T, edge bf and edge cd, creates a graph with three components as shown in .

A very useful characteristic of tree graphs is that the number of edges is always one less than the number of vertices. In fact, any connected graph in which the number of edges is one less than the number of vertices is guaranteed to be a tree. Some examples are given in .

Condensed — the full section is in OpenStax Contemporary Mathematics.

Suppose that you planned to set up your own computer network with four devices. One option is to use a “mesh topology” like the one in , in which each device is connected directly to every other device in the network.

The mesh topology for four devices could be represented by the complete Graph A₁ in where the vertices represent the devices, and the edges represent network connections. However, the devices could be networked using fewer connections. Graphs A₂, A_3, and A₄ of show configurations in which three of the six edges have been removed. Each of the Graphs A₂, A₃ and A₄ in is a tree because it is connected and contains no cycles. Since Graphs A₂, A₃ and A₄ are also subgraphs of Graph A₁ that include every vertex of the original graph, they are also known as spanning trees.

By definition, spanning trees must span the whole graph by visiting all the vertices. Since spanning trees are subgraphs, they may only have edges between vertices that were adjacent in the original graph. Since spanning trees are trees, they are connected and they are acyclic. So, when deciding whether a graph is a spanning tree, check the following characteristics:

• All vertices are included.
• No vertices are adjacent that were not adjacent in the original graph.
• The graph is connected.
• There are no cycles.

Suppose that you wanted to find a spanning tree within a graph. One approach is to find paths within the graph. You can start at any vertex, go any direction, and create a path through the graph stopping only when you can’t continue without backtracking as shown in .

Once you have stopped, pick a vertex along the path you drew as a starting point for another path. Make sure to visit only vertices you have not visited before as shown in .

Repeat this process until all vertices have been visited as shown in .

The end result is a tree that spans the entire graph as shown in .

Notice that this subgraph is a tree because it is connected and acyclic. It also visits every vertex of the original graph, so it is a spanning tree. However, it is not the only spanning tree for this graph. By making different turns, we could create any number of distinct spanning trees.

Another approach to finding a spanning tree in a connected graph involves removing unwanted edges to reveal a spanning tree. Consider Graph D in .

Graph D has 10 vertices. A spanning tree of Graph D must have 9 edges, because the number of edges is one less than the number of vertices in any tree. Graph D has 13 edges so 4 need to be removed. To determine which 4 edges to remove, remember that trees do not have cycles. There are four triangles in Graph D that we need to break up. We can accomplish this by removing 1 edge from each of the triangles. There are many ways this can be done. Two of these ways are shown in .

Condensed — the full section is in OpenStax Contemporary Mathematics.

In many applications of spanning trees, the graphs are weighted and we want to find the spanning tree of least possible weight. For example, the graph might represent a computer network, and the weights might represent the cost involved in connecting two devices. So, finding a spanning tree with the lowest possible total weight, or minimum spanning tree, means saving money! The method that we will use to find a minimum spanning tree of a weighted graph is called Kruskal’s algorithm. The steps for Kruskal’s algorithm are:

Step 1: Choose any edge with the minimum weight of all edges.

Step 2: Choose another edge of minimum weight from the remaining edges. The second edge does not have to be connected to the first edge.

Step 3: Choose another edge of minimum weight from the remaining edges, but do not select any edge that creates a cycle in the subgraph you are creating.

Step 4: Repeat step 3 until all the vertices of the original graph are included and you have a spanning tree.

Condensed — the full section is in OpenStax Contemporary Mathematics.

• A brute force algorithm always finds the ideal solution but can be impractical whereas a greedy algorithm is efficient but usually does not lead to the ideal solution.
• A Hamilton cycle of lowest weight is a solution to the traveling salesperson problem.
• The brute force method finds a Hamilton cycle of lowest weight in a complete graph.
• The nearest neighbor method is a greedy algorithm that finds a Hamilton cycle of relatively low weight in a complete graph.

• The Problem in Good Will Hunting by Numberphile
• Spanning Trees in Graph Theory
• Use Kruskal's Algorithm to Find Minimum Spanning Trees in Graph Theory

• The number of edges in a tree graph with \(n\) vertices is \(n-1\). A connected graph with n vertices and \(n-1\) edges is a tree graph.

Everyone Gets a Turn! – Graph Colorings

Let’s put your knowledge of graph colorings to work! Your task is to plan a field day following these steps.

1. Select between seven and ten activities for your field day. You can look online for ideas.
2. Create a survey asking for the participants to select the three to five events in which they would most like to participate. Survey between seven and ten people.
3. Use the results of your survey to create a graph in which each vertex represents one of the events. A pair of vertices will be adjacent if there is at least one participant who would like to participate in both events.
4. Find a minimum coloring for the graph. Explain how you found it and how you know the chromatic number of the graph.
5. Use your solution to part d to determine the minimum number of timeslots you must use to ensure that everyone has the opportunity to participate in their top three events.
6. Find the complement of the graph you created. Explain what the edges in this graph represent.

A Beautiful Day in the Neighborhood – Euler Circuits

Let’s apply what you have learned to the community in which you live. Using resources such as your county’s property appraiser’s website, create a detailed graph of your neighborhood in which vertices represent turns and intersections. Represent a large enough part of your community to include no fewer than 10 intersections or turns. Then use your graph to answer the following questions.

1. Label the edges of your graph.
2. Determine if your graph is Eulerian. Explain how you know. If it is not, eulerize it.
3. Find an Euler circuit for your graph. Give the sequence of vertices that you found.
4. What does the Euler circuit you found in part c represent for your community?
5. Describe an application for which this Euler circuit might be used.

Dream Vacation – Hamilton Cycles and Paths

Where in the world would you like to travel most: the Eiffel Tower in Paris, a Broadway musical in New York city, a bike tour of Amsterdam, the Tenerife whale and dolphin cruises in the Canary Islands, the Giza Pyramid in Cairo, or maybe the Jokhang Temple in Tibet? Let's plan your dream vacation!

Condensed — the full section is in OpenStax Contemporary Mathematics.