Massachusetts Institute of Technology Lecture 7 6.042J/18.062J: Mathematics for Computer Science September 28, 2000 Professors Nancy Lynch and Srinivas Devadas

Graphs and Trees

Topics for today:

• Graph coloring

• Graph connectivity

• Euler circuits

• Hamiltonian circuits

• Trees

Reading: Rosen, Sections 7.4, 7.5, 7.8, 8.1, 8.2, 8.4, 8.5

1 Graph Coloring

Time to discuss final exams. The MIT Schedules Office needs to assign a time slot for each final. This is not easy, because some students are taking several classes with finals, and a student can take only one test during a particular time slot. The Schedules Office wants to avoid all conflicts, but wants to make the exam period as short as possible.

This scheduling problem can be represented by a graph. Let each vertex represent a course. Put an edge between two vertices if there is some student that is taking both courses. Identify each possible time slot with a color. For example, Monday 9-12 is red, Monday 1-4 is blue, Tuesday 9-12 is green, etc. The problem of assigning time slots to exams is then equivalent to the problem of assigning colors to vertices.

If a student is taking two courses, then there is an edge between two vertices. If these vertices are the same color, then there is a conflict because the student has to take exams for the two courses at the same time. Therefore, the problem is to color each vertex of the graph so that no adjacent vertices have the same color and so that the number of colors used is as small as possible. An example is shown in Figure 1.

In general, the minimum number of colors needed to color the vertices of a graph G so that no two adjacent vertices are the same is called the chromatic number and is written χ(G)^{1}. For example, if G is the 3-cycle or triangle graph, then χ(G) = 3.

In general, finding the chromatic number of a graph is very hard. However, we can at least put some upper bounds on the chromatic number. For example, the chromatic number of an n-vertex graph is certainly at most n, since every vertex could be assigned a different color.

We can do better, however:

Theorem 1.1 Any graph in which the maximum vertex degree is d can be colored with at most d colors.

1This is the Greek letter “chi” pronounced “key” by the ancient Greeks and “kie” by mathematicians and frats.

Figure 1: This graph represents the exam scheduling problem. Each vertex stands for a course. An edge between two vertices indicates that a student is taking both courses and therefore the exams can not be scheduled at the same time. Each exam time slot is associated with a color. A schedule that creates no conflicts corresponds to a coloring of the vertices such that no adjacent vertices receive the same color.

This theorem implies, for example, that a graph with thousands of vertices, each of degree 3, requires at most 4 colors. The proof is surprisingly easy:

Proof. Fix d. The proof is by induction. Let P (n) be the proposition that every graph with n vertices, all with degree at most d, can be colored using at most d + 1 colors.

For the base case, P (1), we consider a single vertex. Clearly, this can be colored with 1 ≤ d + 1 colors.

In the inductive step, assume P (n) to prove P (n + 1). Let G be an n + 1-vertex graph of degree at most d. Let G′ be the graph obtained from G by removing a vertex v and its incident edges. No vertex in G′ has degree greater than d, since removing a vertex and incident edges cannot increase the degree of any other vertex. By induction, we can color G′ with at most d + 1 colors.

Now we need to “put back” the vertex v we removed and color it. But v has at most d neighbors in G. Among them, these other vertices can “use up” at most d colors. Thus, one of our d + 1 candidate colors is still available to color the replaced vertex without violating the coloring rules.

2 Connectivity

Is a graph all in one piece or composed of several pieces? To walk from one vertex to another, how many edges must one cross? Are there many different routes or just one? These are questions about connectivity.

2.1 Basic Notions of Connectivity

Definitions similar to those for digraphs.

In a graph, a path from a vertex u to a vertex v is a sequence of vertices u = u_{0}, u_{1}, u_{2}, …, u_{k} = v, where each (u_{i}, u_{i+1}) is an edge of the graph. A path may contain the same edge or vertex multiple times.

In a simple path, no vertex appears more than once. However, as a special case, the initial and final vertices may be the same. In other words, u_{0}, u_{1}, u_{2}, …, u_{k−1} are all distinct vertices, and u_{1}, u_{2}, …, u_{k} are all distinct vertices, but u_{0} = u_{k} is permitted.

Because we are working with undirected graphs, there is a path from u to v iff there is a path from v to u; one path is obtained from the other by reversing the sequence of edges. The same statement holds for simple paths.

A circuit, or cycle is a path from a vertex back to itself, i.e. a path u = u_{0}, u_{1}, u_{2}, …, u_{k} = v where u = u_{0} = u_{k} = v.

We say two vertices are connected if there is a path between them.

Lemma 2.1 There is a path between two vertices iff there is a simple path between them.

So we could equally well say connected means there is a simple path between them.

Proof. Like the analogous proof for the digraph case.

A graph is connected if there is a path between every pair of distinct vertices. For example, referring back to Figure ??, the empty graph is disconnected, but all others shown are connected.

Theorem 2.2 In any undirected graph, connectedness is an equivalence relation.

Proof. It is reflexive because we allow length 0 paths. It is symmetric because we can reverse paths in an undirected graph. It is transitive because we can concatenate paths.

Like any equivalence relation, connectedness induces a partition of the vertices into equivalence classes. Each equivalence class is called a connected component. A connected component is a set of vertices each of which can reach all the others, and none of which can reach any other vertices.

We can also say that a connected component of a graph is a subgraph that is connected and maximal. This is, if any more vertices are added to the subgraph, then it is no longer connected. For example, every connected graph has exactly one connected component. The empty graph on n vertices has n connected components. A graph with three connected components is shown in Figure 2.

Figure 2: This is a picture of a graph with 3 connected components.

2.2 Cuts

Another way to look at connectivity is to see what prevents it.

Definition 2.3 A cut in a graph G = (V, E) is a partition of the vertices V into two nonempty sets W and V − W. A cut is said to be empty provided that no edge of G connects W and V − W, that is, no edge has one endpoint in each set.

Theorem 2.4 A graph is connected iff it has no empty cuts.

Proof. Show the equivalent proposition: a graph is disconnected iff it has an empty cut.

Suppose G has an empty cut (W, V − W). Let w ∈ W and v ∈ V − W. We show that there is no path from v to w, which implies that G is not connected. We proceed by contradiction: suppose there is a path v = p_{0}, …, p_{k} = w from v to w. Consider the smallest j such that p_{j} ∈ W. (This is using the well ordering principle: the set of j such that p_{j} ∈ W is nonempty since k is in the set, so it has a smallest element j). Note j ≠ 0, so p_{j−1} is a vertex on the path that is not in W. So the edge (p_{j−1}, p_{j}) has one endpoint in W and the other in V − W, contradicting the claim that (W, V − W) is an empty cut.

For the other direction, suppose that G is disconnected and construct an empty cut. By assumption, there is a pair of vertices v and w such that there is no path from v to w. Let W be the set of vertices connected to w (by a path). Then (W, V − W) is an empty cut. For suppose the cut is not empty. Then there is an edge (x, y) with x ∈ W and y ∈ V − W. But there is a path from w to x. Adding the edge (x, y) gives a path from w to y, so y ∈ W. This is a contradiction.

2.3 A False Theorem about Connectivity

If a graph is connected, then every vertex must be connected to some other vertex. Is the converse of this statement true? If every vertex is connected to some other vertex, then is the graph connected? The answer is no. In fact, the graph with three connected components showing in Figure 2 is a counterexample. So what is wrong with the following proof?

False Theorem 1 If every vertex in a graph with at least 2 nodes is adjacent to another vertex, then the graph is connected.

Nothing helps a false proof like a good picture; see Figure 3.

Proof. The proof is by induction. Let P (n) be the predicate that if every vertex in an n-vertex graph is adjacent to another vertex, then the graph is connected. In the base case, P (2) is trivially true.

Figure 3: This picture accompanies the false proof. Two situations are depicted. In one, vertices x_{1} and x_{2} both lie among the first n vertices, and so there is a connecting path by induction. In the second, v = x_{1} and x_{2} is among the first n vertices. In this case there is a connecting path because there is an edge from v to u and a path from u to x_{2} by induction.

In the inductive step, we assume P (n) to prove P (n + 1). Start with an n-vertex graph; this is connected by induction. Now add a vertex v. By assumption v is connected to one of the first n vertices; call that one u.

Now we must show that for every pair of distinct vertices x_{1} and x_{2}, there is a path between them. If both x_{1} and x_{2} are among the first n vertices, then there is a path by induction. Otherwise, one of the vertices is v (say x_{1}) and the other is among the first n vertices. These are connected by the path from x_{1} to u to x_{2} as shown in the figure.

The error is in the early statement “Start with an n-vertex graph; this is connected by induction.” The induction hypothesis does not say that every n-vertex graph is connected, but only, “if every vertex in an n-vertex graph is adjacent to another vertex, then the graph is connected”.

The core problem here is called “buildup error” and is a common source of mistakes in inductive proofs.

The name buildup error arises from the intuition that usually drives the error: that in order to create an instance of size n + 1, you take an instance of size n and extend it by one. If you are careless, you can forget some of the possible ways a size n+1 problem can arise: you fail to “build” all the size n + 1 instances, so your proof doesn’t cover all the instances.

More formally, buildup error occurs when the induction hypothesis P (n) is itself an implication of the form A ⇒ B. In this instance, A is the statement, “every vertex is adjacent to another vertex” and B is the statement, “the graph is connected”.

In the inductive step of a correct proof, we assume A ⇒ B for n in order to prove A ⇒ B for n + 1. In an erroneous proof, we assume B for n in order to prove A ⇒ B for n + 1. This is precisely what happened; we assumed, “the graph is connected” rather than, “if every vertex is adjacent to another vertex, then the graph is connected”.

2.4 Number of Connected Components

Now a true theorem about connectivity...

We start with the common-sense observation that if a graph has too few edges, it cannot contain a path between every pair of vertices. More generally, a graph with a very small number of edges ought to have many connected components. (Remember, “many connected components” does not mean “very connected”; rather, it means “broken into many pieces”!) The following theorem makes these observations concrete.

Theorem 2.5 A graph with k edges and n vertices, where n and k are natural numbers, has at least n − k connected components.

For example, a graph with 0 edges and 20 vertices has at least 20 − 0 = 20 connected components. A graph with 100 vertices and 35 edges must have at least 100 - 35 = 65 connected components. A graph with 35 vertices and 100 edges must have at least 35 - 100 = -65 connected components. (True, but not very interesting.)

The theorem is proved by fixing any generic n, and then working by induction on k. This may seem odd, because for k > n, the theorem says that the number of connected components is greater than some negative number. This is useless, but true, so there is no harm.

Proof. Fix n. The proof is by induction on k, starting from k = 0.

Let P (k) be the predicate that an n-vertex graph with k edges has at least n − k connected components. In the base case, P (0) holds because an n-vertex graph with 0 edges does have at least n − 0 = n components.

For the inductive step, assume that an n-vertex graph with k edges has at least n − k connected components, and try to prove that an n-vertex graph with k + 1 edges has at least n − k − 1 connected components. Let G be a graph with n vertices and k + 1 edges. Remove one edge e, which gives a subgraph G′. The resulting graph G′ has n vertices and k edges. By inductive hypothesis, this graph G′ has at least n − k connected components.

Now consider what happens to the number of connected components when we add the edge e back in. There are two possibilities: e may be incident on two vertices in the same connected component of G′, or two vertices in different connected components of G′.

In the first case, where e is incident on two vertices in the same connected component, then the number of connected components is unchanged when e is added back in, that is, G has at least n − k connected components in this case.

In the second case, where e is incident on vertices in two different connected components of G′, the two become a single connected component when e is added back in. This reduces the number of connected components by exactly one, which implies that there are still at least n − k − 1 connected components in G.

In both cases, the number of connected components is at least n − k − 1, which is what we need to show. If a graph has fewer than n − 1 edges, then the theorem implies it has more than one connected component. Therefore, a graph must have at least n − 1 edges to be connected. In fact, there are graphs with n−1 edges and a single connected component; the line graph of Figure ?? is an example.

Is this a complete proof? Not quite. We claimed that adding one edge between two separate connected components reduces the number of connected components by one. This is obvious by picture, but how do we prove it formally?

Lemma 2.6 If an edge is added that connects two distinct components of a graph, the number of components is reduced by one.

Proof. Suppose the added edge is (v, w), and let [v] and [w] be the connected components containing v and w respectively. We claim that upon adding edge (v, w), we merge [v] and [w] into a single component and affect no other components.

To see that no other component is changed, suppose for contradiction that there is some vertex q not in the component of v or w for which adding (v, w) changes its component–that is, the set of vertices it can reach. There must be a new path from q to some other vertex r. The only way this path can be “new” is if it uses edge (v, w). So both of v and w are on the path from q to r. Suppose without loss of generality that v appears first on the path. Then there is a path from q to v that does not use edge (v, w). This path existed before we added (v, w), meaning that q is in the same component as v. This contradicts our initial assumption.

Corollary 2.7 Deleting a graph edge increases the number of components by at most one.

Proof. Suppose deleting edge e increased the number by more than one. We have just seen that putting e back can decrease the number of components by at most one. So deleting e and putting it back would give a net gain in the number of components! This is a contradiction.

3 Euler Tours

We have already seen Euler circuits for directed graphs—circuits that traverse every edge of the digraph exactly once. We can consider the same kind of problem for undirected graphs.

The Koenigsberg bridge problem: can we cross all seven bridges in the town of Koenigsberg exactly once, without repeats, returning to our starting point?

          |    |           |     /
      ----|----|---   -----|----/
     /    |    |   \ /     |
----<             --X--
     \    |    |   / \     |
      ----|----|--/   \----|----\
          |    |           |     \

Figure 4: Graph representation for the Koenigsberg bridge problem.

This problem has a graph representation as shown in Figure 4

Stated as a general graph theory problem, the problem is to construct a circuit of the graph that traverses every edge exactly once. (Each edge will be traversed in exactly one direction.) (Actually, note that the Koenigsberg graph is technically a multigraph, not a simple graph, because it has multiple edges between two of the pairs of vertices. We could change this into a simple graph by adding some extra vertices in the middle of the repeated edges.) Euler, 1736, proved that it can’t be done. So we call such tours “Euler Tours.”

Theorem 3.1 If undirected graph G has Euler tour, then G is connected and every vertex has even degree.

Proof. Direct every edge according to tour. We enter a vertex as many times as we leave it. So every vertex must have indegree equal to outdegree. So total even.

100 years later, Hierholzer proved the converse (that’s the trouble with coming second—no one remembers your name!)

Theorem 3.2 If G is connected and every node has even degree, then it has an Euler tour.

Proof. If G has only one node then it has a trivial (1-node) Euler tour. So assume G has at least two nodes. Then G must have at least one edge.

Starting from this edge, construct a circuit with no repeated edges: trace from node to node until we cannot go any further on an unused edge. (Example) Because every node has even degree, this can only happen when we return to the node we started at (every other node we reach will have another edge by which we may leave).

Let C be the longest circuit without any repeated edges. If C includes all the edges of G, we are done. So assume it doesn’t. Let H be the subgraph of G consisting of all the edges of G that aren’t in C, and all the nodes of G that are incident on these edges. Claim that some node u in H is also in C. Why? Because G is connected.

Now choose any edge of H incident upon u.

Starting with that edge, construct a cycle in H, following the same procedure as above. Eventually, it has to get back to its starting point u. Now we have two cycles with disjoint edge sets and a common vertex u. Splice them together to get a larger cycle than C. Contradicts choice of C as maximum.

4 Hamiltonian Circuits

A slightly different question: is there a simple circuit that traverses every vertex exactly once? Such a circuit is called a Hamiltonian circuit (Hamiltonian cycle). Similarly, a simple path that traverses every vertex exactly once is a Hamiltonian path.

Small change from the Euler circuit question, but suddenly, instead of answer being trivial, it becomes very complicated. It is believed that there is no simple criterion to determine whether or not a graph has a Hamiltonian circuit; in fact, it is believed that no computer program can answer this question efficiently (it is NP-complete).

The book has some simple criteria for existence and nonexistence of Hamiltonian cycles. Here is a slightly harder result.

Lemma 4.1 Any graph with n vertices, n ≥ 3, in which the minimum degree of each node is at least n/2, has a Hamiltonian circuit.

Proof. By contradiction. Suppose some graph has n vertices, n ≥ 3, and the minimum degree of each node is at least n/2, but that graph does not have a Hamiltonian circuit. If we add edges to this graph one at a time, we eventually end up with a complete graph, which does have a Hamiltonian circuit. (Why?) Somewhere in the process of adding edges, we have a graph G that doesn’t have a Hamiltonian circuit, but adding one more edge (u, v) yields a graph G′ that does have a Hamiltonian circuit. We’ll get a contradiction for this G.

Since G plus the one edge (u, v) has a Hamiltonian circuit, G alone has a Hamiltonian path from u to v (just remove the one new edge). Write u = u_{1}, …, u_{n} = v, includes all the nodes of G.

Now let’s play with that path and turn it into a circuit, to get a contradiction. We will use the fact that u and v each have degree at least n/2 to produce two edges to replace one edge (u_{i}, u_{i+1}) on the path...

Now let’s count: Of the n − 2 intermediate nodes on the path u_{2}, …, u_{n−1} (all but the first and last) we know that at least n/2 are neighbors of u, and at least n/2 are neighbors of v. So it can be shown that there are two adjacent nodes, u_{i} and u_{i+1}, where u_{i} is a neighbor of v and u_{i+1} is a neighbor or u.

Figure 5: Converting the Hamiltonian path into a circuit

Postpone this for a minute... Then cut and add edges, to produce a Hamiltonian circuit, contradiction.

Now, how do we get u_{i} and u_{i+1}? Just count how many are in various sets. Use a little trick: Let S be {i : u_{i+1} is a neighbor of u}. Let T be {i : u_{i} is a neighbor of v}. Each of S and T has at least n/2 elements. Since there are only n − 2 possible values of i, some i must be in both sets. That is, u_{i} is a neighbor of v and u_{i+1} is a neighbor of u.

This gives a special class of graphs with Hamiltonian circuits. But no one has nice criteria for finding Hamiltonian circuits in general, or for determining if they exist.

5 Trees

Important special type of graph for CS applications. Trees are the “smallest” connected graphs, in the sense that they have the fewest edges required for connectivity. We will provide definitions and basic properties, including looking at some alternative definitions and showing they are equivalent.

We will count numbers of vertices and edges.

We will relate trees to graphs, by talking about spanning trees and spanning forests.

We will show some places where trees are used in computer science: Decision trees, binary search trees, parse trees, tree-structured file systems,...

5.1 Basic definitions

Definition 5.1 A tree is a connected (undirected) graph with no simple circuits of length > 2.

Figure 6: This tree has 11 “leaves”, which are defined as vertices of degree at most one. The remaining 7 vertices are called “internal nodes”.

The vertices in a tree can be classified into two categories. Vertices of degree at most one are called leaves, and vertices of degree greater than one are called internal nodes.

Trees can be defined several different ways, as the following lemma shows.

Lemma 5.2 The following properties of a graph G are equivalent (each implies the others):

1. G is a connected graph with no simple circuits of length > 2 (a tree, as defined above).

2. G is a connected graph that is disconnected by the removal of any edge, i.e., a “minimal” connected graph.

3. G is a graph with a unique simple path between every pair of distinct vertices.

Since the definitions are equivalent, any one of them could be taken as the definition of a tree. Theorems asserting that several mathematical statements are equivalent are quite common. One way to prove such a theorem would be to consider every pair of statements in turn and prove them equivalent. That is, we would prove 1 ⇔ 2, 2 ⇔ 3, and 3 ⇔ 1. This would be overkill. A simpler approach is to show 1 ⇒ 2, 2 ⇒ 3, and 3 ⇒ 1. These three implications are sufficient to prove every pair of statements equivalent. For example, 2 ⇔ 3 follows because we prove 2 ⇒ 3 directly, and prove 3 ⇒ 2 with the two steps 3 ⇒ 1 ⇒ 2.

Lemma 5.3 (1 ⟹ 2) A connected graph with no simple circuits of length > 2 is disconnected by the removal of any edge.

Proof. By contradiction. Suppose we can delete edge (u, v) without disconnecting the graph. This means there is a path from u to v that doesn’t use (u, v). Therefore, there is a simple path from u to v that doesn’t use (u, v). Adding edge (u, v) to this simple path creates a simple circuit. This contradicts the claim of no simple circuits.

Lemma 5.4 (3 ⟹ 1) A graph with a unique simple path between any pair of nodes is connected and has no simple circuits of length > 2.

Proof. It clearly meets the definition of connectivity. To see there are no simple circuits we argue by contradiction. Suppose we have a simple circuit v_{1}, v_{2}, …, v_{k}, v_{1} of length > 2. Then there are 2 simple paths from v_{1} to v_{k}, namely v_{1}, …, v_{k} and the edge (v_{1}, v_{k}).

Lemma 5.5 (2 ⟹ 3) A connected graph that is disconnected by the removal of any edge has a unique simple path between any pair of vertices.

Proof. We prove the contrapositive. Suppose there are two different simple paths from u to v. Call one P_{1}: u = x_{0}, x_{1}, …, x_{k} = v. Call the other P_{2}: u = y_{0}, …, y_{l} = v. Let i be the smallest such that x_{i} ≠ y_{i} (why does this have to exist?). Claim: we can remove the edge (y_{i−1}, y_{i}) without disconnecting G. To see this, consider any pair of vertices z and w. There’s a simple path between them at the start. It remains to show there’s still a path (doesn’t need to be simple) after removing (y_{i−1}, y_{i}). We use proof by cases.

Case 1: (y_{i−1}, y_{i}) wasn’t on the path. Then the path remains after removing (y_{i−1}, y_{i}).

Case 2: (y_{i−1}, y_{i}) was on the path. WLOG, y_{i−1} is encountered first. So the path looked like z, …, y_{i−1}, y_{i}, …, w. So there’s a different path: go from z to y_{i−1} on the first part of z-w path, then from y_{i−1} to u on the first part of P_{2}, then from u to v on P_{1}, then from v to y_{i} on the second part of P_{2}, then from y_{i} to w on the second part of the z-w path.

5.2 Counting tree nodes and edges

Definition 5.6 A leaf is a node of degree 1.

Lemma 5.7 Any tree with more than one vertex has at least one leaf.

Proof. Consider a longest simple path v_{1}, …, v_{k} (why does such exist?). Claim v_{1} is a leaf. Proof: suppose not. Then v_{1} has a second neighbor x. Is x = v_{i} for some i? No, that would give a simple cycle of length > 2. Thus x, v_{1}, …, v_{k} is a longer simple path, a contradiction.

The following is “obvious,” but I’ll write down a proof for those who want to read it.

Lemma 5.8 If we remove a leaf and its edge from a tree, we get a tree.

Proof. Suppose we remove leaf v and its one incident edge (u, v). We need to show the remaining graph is still connected (it is clearly still acyclic). Consider the unique simple path between two other vertices x and y. Can (u, v) be on this path? No, because (u, v) is the only edge incident on v, so we would have to traverse it twice to enter and leave v. This would make a non-simple path.

Since (u, v) is not on the path from x to y, there is still a path after we delete (u, v). This is true for all pairs x and y, so the remaining graph is connected.

Lemma 5.9 Any tree on n vertices has n − 1 edges.

Proof. By induction on n, starting from n = 1. Base case is trivial. Inductive step: Start with an arbitrary tree with n + 1 nodes. Remove one node and its incident edge. By the previous lemma, the result is a tree (with n nodes). By the inductive hypothesis, this tree has n−1 edges. So the original tree has n edges.

Lemma 5.10 Any n vertex connected graph G with n − 1 edges is a tree.

Proof. Let’s use the second definition of a tree—minimal connected graph. We are assuming that G is connected. We must show that if we remove any edge from G, the resulting graph is disconnected.

Since G has n − 1 edges, removing any edge reduces the number of edges below n − 1. But we proved earlier that to be connected (have one connected component) a graph must have at least n − 1 edges. So that means that removing any edge disconnects the graph.

So, we actually have yet another equivalent definition of a tree: a connected graph with n nodes and n − 1 edges (for some n).

5.3 Spanning Trees and Forests

This subsection wasn’t covered in lecture, but will be covered in Friday’s tutorial.

We’ve just seen that the “minimal” (poset, under edge containment) connected graphs are trees. It turns out that every connected graph contains a tree:

Definition 5.11 A spanning tree of a graph is a subset of the graph edges that forms a tree on all the graph nodes.

Example

Notice that the notion “tree” is an intrinsic concept (cares only about the nodes adjacent to the edges of the tree), while “spanning tree” is extrinsic (cares about whether you have all the graph’s nodes).

Lemma 5.12 Every connected graph contains a spanning tree.

Proof. By contradiction. Suppose there is some counterexample, and use well-ordering to obtain a counterexample graph G with the fewest edges. Because it’s a counterexample, G is connected, but has no spanning tree.

There are two cases:

1. You can delete some edge from G and stay connected. Then you get a smaller counterexample (still have no spanning tree). That contradicts the way G was chosen.

2. Any way of deleting an edge disconnects G. But that means that G itself is a tree. (Second definition of tree). So G does have a spanning tree (itself). Contradiction.

Example: The notion of a spanning tree arises in computer network graphs. A network graph generally connects nodes by multiple paths, in order to tolerate failures, changes in the network, and congestion. But during relatively stable, lightly-loaded periods of time, it’s desirable to minimize the amount of communication, and conduct the communication on predictable paths. For this purpose, a spanning tree of the portion of the network involved in some application is generally constructed (e.g., IP Multicast does this) and used for communication.

Some graphs aren’t connected; they don’t have spanning trees. Instead, they have spanning forests:

Definition 5.13 A forest is any acyclic graph.

Lemma 5.14 Each connected component of a forest is a tree.

Proof. Each connected component of a forest is connected and acyclic.

Definition 5.15 A spanning forest for a graph G is a forest that connects every pair of vertices that were connected in G,

Example Thus, a spanning forest G is just a collection of trees, one spanning each connected component of G.

5.4 Rooted Trees

Trees in CS (and elsewhere) are often drawn in a particular orientation, one node at the top, called the root, and the others on paths moving downward. (Of course, real trees, like maples, etc., have the root at the bottom, but no one in CS seems to have noticed this.)

This depends on distinguishing one node, any node, as root. Level 0 node. Then all its neighbors drawn just below it, level 1. Then all their neighbors, level 2, etc.

Rooted tree = undirected tree + root. Maximum level number = height of rooted tree.

Sometimes “orient” (direct) all the edges downward, producing a directed tree. Note different roots yield different directed trees (could even have different heights).

Example

Terminology: Parent, sibling, ancestor, descendent. From genealogy. Subtree.

Note: Changing the order of siblings doesn’t change the tree.

Examples of uses of rooted trees:

Representing organization structure (who reports to whom).

Representing computer file systems (UNIX, almost) Each internal node corresponds to a directory, and each leaf corresponds to a file. If one directory contains another, there there is an edge between the associated internal nodes. If a directory contains a file, then there there is an edge between the internal node and a leaf.

See more later.

Some special kinds of rooted trees: m-ary, full m-ary, complete m-ary

Definition: An m-ary tree, m ≥ 1, is a rooted tree in which every internal vertex has no more than m children.

Special case where m = 2 is binary tree. Almost the same as we defined earlier in term (as an example to illustrate recursive definitions and structural induction). Slight difference: Now we’re not distinguishing left and right. (If we want to do this, we should call the structure an ordered rooted tree instead of just a rooted tree.)

Definition: A full m-ary tree is an m-ary tree in which each internal node has exactly m children. (However, all leaves need not be at the same level.) A complete m-ary tree is a full m-ary tree in which all the leaves are at the same level.

Examples

5.5 Counting on rooted trees

What can we say about number of vertices, edges, internal vertices, leaves, etc., in m-ary trees? Fix some values. Suppose that T is a full m-ary tree (m ≥ 2) with l leaves, i internal nodes, e edges, and n total nodes. Start with the most restrictive case, complete m-ary trees:

Theorem 5.16 For a complete m-ary tree (m ≥ 2):

1. l = m^{h}.

2. i = \frac{m^{h}−1}{m−1}

3. n = \frac{m^{h+1}−1}{m−1}

4. e = \frac{m^{h+1}−1}{m−1} − 1

Proof.

1. l = m^{h}

By induction on h.

Base: h = 0: 1 = m^{0} leaves.

Inductive step: Assume for h, prove for h + 1.

Given tree T of height h+1, children subtrees have height h, so by inductive hypothesis, each has m^{h} leaves. Leaves of whole tree are exactly the leaves of the subtrees. So m × m^{h}, which = m^{h+1}, as needed.

2. Again, use induction on h.

3. Again, use induction on h.

4. Use the previous part and the fact that e = n − 1.

For a full, but not necessarily complete, tree, things are a little more complicated:

Theorem 5.17 For a full m-ary tree (m ≥ 2):

1. (n in terms of i.) n = mi + 1.

2. (i in terms of n.) i = \frac{n−1}{m}.

3. (l in terms of n) l = \frac{(m−1)n+1}{m}.

4. (n in terms of l) n = \frac{ml−1}{m−1}.

5. (l in terms of i) l = (m − 1)i + 1.

6. (i in terms of l) i = \frac{l−1}{m−1}.

Proof.

1. Every vertex except the root is the child of an internal vertex. So n is equal to 1 plus the number of child vertices. Claim there are exactly mi child vertices, since there are i internal vertices and each has exactly m children.

2. Just solve the previous for i.

3. Combine obvious fact l = n − i and previous part.

4. Solve previous for n.

5. Combine obvious fact and part 1.

6. Solve previous for i.

These exact results can be used to get inequalities for arbitrary m-ary trees, for example:

1. l ≤ m^{h}.

2. i ≤ \frac{m^{h}−1}{m−1}

3. n ≤ \frac{m^{h+1}−1}{m−1}

4. e ≤ \frac{m^{h+1}−1}{m−1} − 1

5. n ≤ mi + 1.

6. i ≥ \frac{n−1}{m}.

7. l ≤ \frac{(m−1)n+1}{m}.

8. n ≥ \frac{ml−1}{m−1}.

9. l ≤ (m − 1)i + 1.

10. i ≥ \frac{l−1}{m−1}.

Proof: LTTR.

5.6 Applications of Trees

5.6.1 Binary Search Trees

To aid in storing and searching for data. Store data with keys from totally ordered set, at nodes of ordered binary tree. Do this to make it fast to insert and look up items using their keys. Invariant property to maintain: Any value occurring in left subtree of node is < value at node. Any value in right subtree of node is > value at node.

Example

Fast for searching. E.g. to see if m is in tree, compare from top, go left if less, go right if greater, etc.; trace and reach it. E.g., to see if n is in tree, trace – not there. The beauty is that the whole tree need not be searched, just one path. Usually faster, unless tree is very skewed.

Figure 7: A binary search tree

Fast also for insertion of new data. Trace.

Deletion may leave empty nodes, needs special reorganization methods. See in 6.046.

5.6.2 Compiling

Very important use of trees is to represent programs, and pieces of programs, internally during the compilation process. Trees give the structure of the program, which is not made explicit in a linear text representation.

Example: Arithmetic expressions

E.g., (2 + x) - (3 - (x + y)) Ordered tree.

Figure 8: Parse tree for above arithmetic expression

Example: More interesting program structure:

if x > y then while x <= 5 do x := x+1; a:= a^2

This kind of tree is called a parse tree. It is produced during the compilation process, by a compiler program.

Besides containing such structural information, it gets decorated with other information, like the types of the variables. It is then used as the basis for generating machine code.

5.6.3 Decision Trees

Can represent the decision structure of a program. Unwind loops, represent as tree.

Example: Sorting a list of 4 numbers a, b, c, d (assume unequal)

Figure 9: Decision tree for sorting

Answers at bottom. Height of tree corresponds closely to worst-case running time.