Combinatorics Through Guided Discovery

Subsection 2.3.1 Undirected graphs

In Section 1.3.4 we introduced the idea of a directed graph. Graphs consist of vertices and edges. We describe vertices and edges in much the same way as we describe points and lines in geometry: we don't really say what vertices and edges are, but we say what they do. We just don't have a complicated axiom system the way we do in geometry. A graph consists of a set \(V\) called a vertex set and a set \(E\) called an edge set. Each member of \(V\) is called a vertex and each member of \(E\) is called an edge. Associated with each edge are two (not necessarily different) vertices called its endpoints. We draw pictures of graphs by drawing points to represent the vertices and line segments (curved if we choose) whose endpoints are at vertices to represent the edges. In Figure 2.3.1 we show three pictures of graphs.

Each gray circle in the figure represents a vertex; each line segment represents an edge. You will note that we labeled the vertices; these labels are names we chose to give the vertices. We can choose names or not as we please. The third graph also shows that it is possible to have an edge that connects a vertex (like the one labeled \(y\)) to itself or it is possible to have two or more edges (like those between vertices \(v\) and \(y\)) between two vertices. The degree of a vertex is the number of times it appears as the endpoint of edges; thus the degree of \(y\) in the third graph in the figure is four.

Subsection 2.3.2 Walks and paths in graphs

A walk in a graph is an alternating sequence \(v_0e_1v_1\ldots e_iv_i\) of vertices and edges such that edge \(e_i\) connects vertices \(v_{i-1}\) and \(v_i\text{.}\) A graph is called connected if, for any pair of vertices, there is a walk starting at one and ending at the other.

Subsection 2.3.3 Counting vertices, edges, and paths in trees

Problem 111

How many trees are there on the vertex set \(\{1,2\}\text{?}\) On the vertex set \(\{1,2,3\}\text{?}\) When we label the vertices of our tree, we consider the tree which has edges between vertices 1 and 2 and between vertices 2 and 3 different from the tree that has edges between vertices 1 and 3 and between 2 and 3. See Figure 2.3.2.

How many (labeled) trees are there on four vertices? You don't have a lot of data to guess from, but try to guess a formula for the number of labeled trees with vertex set \(\{1,2,\cdots,n\}\text{.}\)

Hint

When you get to four and especially five vertices, draw all the unlabeled trees you can think of, and then figure out in how many different ways you can put labels on the vertices.

We are now going to introduce a method to prove the formula you guessed. Given a tree with two or more vertices, labeled with positive integers, we define a sequence \(b_1,b_2,\ldots\) of integers inductively as follows: If the tree has two vertices, the sequence consists of one entry, namely the label of the vertex with the larger label. Otherwise, let \(a_1\) be the lowest numbered vertex of degree 1 in the tree. Let \(b_1\) be the label of the unique vertex in the tree adjacent to \(a_1\) and write down \(b_1\text{.}\) For example, in the first graph in Figure 2.3.1, \(a_1\) is 1 and \(b_1\) is 2. Given \(a_1\) through \(a_{i-1}\text{,}\) let \(a_i\) be the lowest numbered vertex of degree 1 in the tree you get by deleting \(a_1\) through \(a_{i-1}\)and let \(b_i\) be the unique vertex in this new tree adjacent to \(a_i\text{.}\) For example, in the first graph in Figure 2.3.1, \(a_2=2\) and \(b_2=3\text{.}\) Then \(a_3=5\) and \(b_3=4\text{.}\) We use \(b\) to stand for the sequence of \(b_i\)s we get in this way. In the tree (the first graph) in Figure 2.3.1, the sequence \(b\) is 2344378. (If you are unfamiliar with inductive (recursive) definition, you might want to write down some other labeled trees on eight vertices and construct the sequence of \(b_i\)s.)

The sequence \(b_1,b_2,\ldots, b_{n-2}\) in Problem 112 is called a Prüfer coding or Prüfer code for the tree. There is a good bit of interesting information encoded into the Prüfer code for a tree.

Subsection 2.3.4 Spanning trees

Many of the applications of trees arise from trying to find an efficient way to connect all the vertices of a graph. For example, in a telephone network, at any given time we have a certain number of wires (or microwave channels, or cellular channels) available for use. These wires or channels go from a specific place to a specific place. Thus the wires or channels may be thought of as edges of a graph and the places the wires connect may be thought of as vertices of that graph. A tree whose edges are some of the edges of a graph \(G\) and whose vertices are all of the vertices of the graph \(G\) is called a spanning tree of \(G\text{.}\) A spanning tree for a telephone network will give us a way to route calls between any two vertices in the network. In Figure 2.3.3 we show a graph and all its spanning trees.

Subsection 2.3.5 Minimum cost spanning trees

Our motivation for talking about spanning trees was the idea of finding a minimum number of edges we need to connect all the edges of a communication network together. In many cases edges of a communication network come with costs associated with them. For example, one cell-phone operator charges another one when a customer of the first uses an antenna of the other. Suppose a company has offices in a number of cities and wants to put together a communication network connecting its various locations with high-speed computer communications, but to do so at minimum cost. Then it wants to take a graph whose vertices are the cities in which it has offices and whose edges represent possible communications lines between the cities. Of course there will not necessarily be lines between each pair of cities, and the company will not want to pay for a line connecting city \(i\) and city \(j\) if it can already connect them indirectly by using other lines it has chosen. Thus it will want to choose a spanning tree of minimum cost among all spanning trees of the communications graph. For reasons of this application, if we have a graph with numbers assigned to its edges, the sum of the numbers on the edges of a spanning tree of \(G\) will be called the cost of the spanning tree.

The method you used in Problem 118 is called a greedy method, because each time you made a choice of an edge, you chose the least costly edge available to you.

Subsection 2.3.6 The deletion/contraction recurrence for spanning trees

There are two operations on graphs that we can apply to get a recurrence (though a more general kind than those we have studied for sequences) which will let us compute the number of spanning trees of a graph. The operations each apply to an edge \(e\) of a graph \(G\text{.}\) The first is called deletion; we delete the edge \(e\) from the graph by removing it from the edge set. Figure 2.3.4 shows how we can delete edges from a graph to get a spanning tree.

The second operation is called contraction.

Contractions of three different edges in the same graph are shown in Figure 2.3.5. Intuitively, we contract an edge by shrinking it in length until its endpoints coincide; we let the rest of the graph “go along for the ride.” To be more precise, we contract the edge \(e\) with endpoints \(v\) and \(w\) as follows:

1. remove all edges having either \(v\) or \(w\) or both as an endpoint from the edge set,

2. remove \(v\) and \(w\) from the vertex set,

3. add a new vertex \(E\) to the vertex set,

4. add an edge from \(E\) to each remaining vertex that used to be an endpoint of an edge whose other endpoint was \(v\) or \(w\text{,}\) and add an edge from \(E\) to \(E\) for any edge other than \(e\) whose endpoints were in the set \(\{v,w\}\text{.}\)

We use \(G-e\) (read as \(G\) minus \(e\)) to stand for the result of deleting \(e\) from \(G\text{,}\) and we use \(G/e\) (read as \(G\) contract \(e\)) to stand for the result of contracting \(e\) from \(G\text{.}\)

Problem 119

(a)

How do the number of spanning trees of \(G\) not containing the edge \(e\) and the number of spanning trees of \(G\) containing \(e\) relate to the number of spanning trees of \(G-e\) and \(G/e\text{?}\)

Hint

If you have a spanning tree of \(G\) that contains \(e\text{,}\) is the graph that results from that tree by contracting \(e\) still a tree?

(b)

Use \(\#(G)\) to stand for the number of spanning trees of \(G\) (so that, for example, \(\#(G/e)\) stands for the number of spanning trees of \(G/e\)). Find an expression for \(\#(G)\) in terms of \(\#(G/e)\) and \(\#(G-e)\text{.}\) This expression is called the deletion-contraction recurrence.

(c)

Use the recurrence of the previous part to compute the number of spanning trees of the graph in Figure 2.3.6.

Subsection 2.3.7 Shortest paths in graphs

Suppose that a company has a main office in one city and regional offices in other cities. Most of the communication in the company is between the main office and the regional offices, so the company wants to find a spanning tree that minimizes not the total cost of all the edges, but rather the cost of communication between the main office and each of the regional offices. It is not clear that such a spanning tree even exists. This problem is a special case of the following. We have a connected graph with nonnegative numbers assigned to its edges. (In this situation these numbers are often called weights.) The (weighted) length of a path in the graph is the sum of the weights of its edges. The distance between two vertices is the least (weighted) length of any path between the two vertices. Given a vertex \(v\text{,}\) we would like to know the distance between \(v\) and each other vertex, and we would like to know if there is a spanning tree in \(G\) such that the length of the path in the spanning tree from \(v\) to each vertex \(x\) is the distance from \(v\) to \(x\) in \(G\text{.}\)