We shall look at two more applications of graphs, involving spanning trees and graph colorings. We shall conclude with an interesting example that shows there is more information in graph structure than you might think.

Trees

We defined a tree to be a connected graph that contains no cycles. Trees occur in a number of applications, and we shall examine some of them here.

We begin with a few examples.

Sample Problem 1.1 Which of the following graphs are trees?

Solution. Graph (a) is a tree. Graph (b) is not a tree because it is not connected,  although this might not be obvious immediately. Graph (c) contains a cycle, so it is not a tree.

Your Turn. Which of the following graphs are trees?

The tree diagrams used in (Probability) are just trees laid out in a certain way. To form a tree diagram from a tree, select any vertex as a starting point. Draw edges to all of its neighbors. These are the first generation. Then treat each neighbor as if it were the starting point; draw edges to all its neighbors except the start. Continue in this way; to each vertex, attach all of its neighbors except for those that have already appeared in the diagram. The diagram used in constructing all Hamilton cycles, in (Graphs: Visiting Vertices), is also a tree diagram.

Every path is a tree. Another special type of tree is called a star; this is a complete bipartite graph with only one vertex in one of its parts, or K_1,n.

A tree is a minimal connected graph in the following sense: if any vertex of degree at least 2, or any edge, is deleted, then the resulting graph is not connected.

In fact it is easy to prove that a connected graph is a tree if and only if every edge has this property.

Trees can also be characterized among connected graphs by their number of edges: a tree has precisely one fewer edge than it has vertices. We shall prove this as a formal theorem.

The proof is an example of the technique called proof by contradiction. Suppose you want to prove that a certain statement is true. You start by assuming the statement is false. Then you make some deductions using your assumption. Eventually you “prove” something that you know is false—for example, that a certain number is both odd and even, or that 0 = 1. Something must be wrong with your argument,  and the only candidate is your assumption. So the assumption is wrong; the original statement must have been true, not false.

Theorem 1. A finite connected graph G with v vertices is a tree if and only if it has exactly v−1 edges.

Proof.

(i) Let us call a tree irregular if its number of vertices is not greater by 1 than its number of edges. We shall assume that at least one irregular tree exists, and show that a contradiction follows.

There must be a smallest possible value v for which there is an irregular tree on v vertices, and let G be an irregular tree with v vertices. This value v must be at least 2, because the only graph with one vertex is K1, which has v − 1(= 0) edges.  Choose an edge in G (G must have an edge, or it will simply be a collection of v vertices, with no edges joining them, and will not be connected) and delete it. The result is a union of two disjoint components, each of which is a tree with fewer than v vertices; say the first component has v1 vertices and the second has v₂, where v₁ +v₂ = v. Neither of these graphs is irregular, so they have v₁ −1 and v₂ −1 edges

respectively. Adding one edge for the one that was deleted, we find that the number of edges in G is

                                     (v₁ −1)+(v₂ −1) +1 = v−1.

This contradicts the assumption that G was irregular. So there can be no irregular trees; we could not even choose one smallest example. We have shown that a finite connected graph G with v vertices is a tree only if it has exactly v−1 edges.

 (ii) On the other hand, suppose G is connected but is not a tree. Select an edge that is part of a cycle, and delete it. If the resulting graph is not a tree, repeat the process. Eventually the graph remaining will be a tree, and must have v−1 edges. So the original graph had more than v−1 edges.

Suppose the tree has v vertices. It then has v − 1 edges. As we saw in (Graphs: Traversing Roads)  the sum of all degrees of the vertices equals twice the number of edges, or 2(v−1).

There can be no vertex of degree 0, since the tree is connected and it is not K1; if v − 1 of the vertices have degree at least 2, then the sum of the degrees is at least 1 + 2(v − 1), which is impossible. So there must be two (or more) vertices with degree 1.

An example of a tree with exactly two vertices of degree 1 is the path Pv, provided v > 1. The star K1,n has n vertices of degree 1.

Sample Problem 1.2 Find all trees with five vertices.

Solution. If a tree has five vertices, then the largest possible degree is 4. Moreover there are 4 edges (by Theorem 1), so the sum of the five degrees is 8. As there are no vertices of degree 0 and at least two vertices of degree 1, the list of degrees must be one of

4,1,1,1,1 3,2,1,1,1 2,2,2,1,1.

In the first case, the only solution is the star K_1,4. If there is one vertex of degree 3, no two of its neighbors can be adjacent (this would form a cycle), so the fourth edge must join one of those three neighbors to the fifth vertex. The only case with the third degree list is the path P5. These three cases are