###### Problem 100

In the graph on the left in FigureĀ 2.3.1, what is the degree of each vertex?

\(\newcommand{\cycle}[1]{\arraycolsep 5 pt
\left(\begin{array}#1\end{array}\right)}
\newcommand{\importantarrow}{\Rightarrow}
\newcommand{\qchoose}[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}_q}
\def\neg1choose#1#2{\genfrac{[}{]}{0pt}{}{#1}{#2}_{-1}}
\newcommand{\bp}{
\begin{enumerate}{\setcounter{enumi}{\value{problemnumber}}}}
\newcommand{\ep}{\setcounter{problemnumber}{\value{enumi}}
\end{enumerate}}
\newcommand{\ignore}[1]{}
\renewcommand{\bottomfraction}{.8}
\renewcommand{\topfraction}{.8}
\newcommand{\apple}{\text{š}}
\newcommand{\ap}{\apple}
\newcommand{\banana}{\text{š}}
\newcommand{\ba}{\banana}
\newcommand{\pear}{\text{š}}
\newcommand{\pe}{\pear}
\DeclareMathOperator{\Fix}{Fix}
\DeclareMathOperator{\Orb}{Orb}
\newcommand{\F}{\mathcal{F}}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\)

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.

In the graph on the left in FigureĀ 2.3.1, what is the degree of each vertex?

For each graph in FigureĀ 2.3.1 is the number of vertices of odd degree even or odd?

The sum of the degrees of the vertices of a (finite) graph is related in a natural way to the number of edges.

What is the relationship?

Hint

There are several ways to see how to do this problem. One is to draw pictures of graphs with one edge, two edges, three edges, perhaps four edges and figure out the sum of the degrees. Another is to ask what deleting an edge does to the sum of the degrees. Another is to ask what a given edge ācontributesā to the sum of the degrees.

Find a proof that what you say is correct that uses induction on the number of edges.

Hint

To make your inductive step, think about what happens to a graph if you delete an edge.

Find a proof that what you say is correct that uses induction on the number of vertices.

Find a proof that what you say is correct that does not use induction.

Hint

Suppose that instead of summing the degree of \(v\) over all vertices \(v\text{,}\) you sum some quantity defined for each edge \(e\) over all the edges.

What can you say about the number of vertices of odd degree in a graph?

Hint

Whatever you say should be consistent with what you already know about degrees of vertices.

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.

Which of the graphs in FigureĀ 2.3.1 is connected?

A path in a graph is a walk with no repeated vertices. Find the longest path you can in the third graph of FigureĀ 2.3.1.

A cycle in a graph is a walk whose first and last vertex are equal but which has no other repeated vertices. Which graphs in FigureĀ 2.3.1 have cycles? What is the largest number of edges in a cycle in the second graph in FigureĀ 2.3.1? What is the smallest number of edges in a cycle in the third graph in FigureĀ 2.3.1?

A connected graph with no cycles is called a tree. Which graphs, if any, in FigureĀ 2.3.1 are trees?

Draw some trees and on the basis of your examples, make a conjecture about the relationship between the number of vertices and edges in a tree. Prove your conjecture. (Hint: what happens if you choose an edge and delete it, but not its endpoints?)

Hint

What happens if you choose an edge and delete it, but not its endpoints?

What is the minimum number of vertices of degree one in a finite tree? What is it if the number of vertices is bigger than one? Prove that you are correct.

Hint

One approach to the problem is to use facts that we already know about degrees, vertices and edges. Another approach is to try deleting an edge from a tree with more than one vertex and analyze the possible numbers of vertices of degree one in what is left over.

In a tree, given two vertices, how many paths can you find between them? Prove that you are correct.

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

How long will the sequence of \(b_i\)s be if it is computed from a tree with \(n\) vertices (labeled with 1 through \(n\))?

What can you say about the last member of the sequence of \(b_i\)s?

Hint

Do some examples.

Can you tell from the sequence of \(b_i\)s what \(a_1\)is?

Hint

Is it possible for \(a_1\) to be equal to one of the \(b_j\)s?

Find a bijection between labeled trees and something you can ācountā that will tell you how many labeled trees there are on \(n\) labeled vertices.

Hint

You have seen that the sequence \(b\) determines \(a_1\text{.}\) Does it determine any other \(a_j\)s? If you knew all the \(a_j\)s and all the \(b_j\)s, could you reconstruct the tree? What are the possible values of \(b_1\text{?}\) \(b_j\text{?}\)

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.

What can you say about the vertices of degree one from the PrĆ¼fer code for a tree labeled with the integers from 1 to \(b\text{?}\)

Hint

What vertex or vertices in the sequence \(b_1,b_2,\ldots,b_{n-1}\) can have degree 1?

What can you say about the PrĆ¼fer code for a tree with exactly two vertices of degree 1? (and perhaps some vertices with other degrees as well)? Does this characterize such trees?

What can you determine about the degree of the vertex labeled \(i\) from the PrĆ¼fer code of the tree?

Hint

If a vertex has degree 1, how many times does it appear in the PrĆ¼fer code of the tree? What about a vertex of degree 2?

What is the number of (labeled) trees on \(n\) vertices with three vertices of degree 1? (Assume they are labeled with the integers 1 through \(n\text{.}\)) This problem will appear again in the next chapter after some material that will make it easier.

Hint

How many vertices appear exactly once in the PrĆ¼fer code of the tree and how many appear exactly twice?

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.

Show that every connected graph has a spanning tree. It is possible to find a proof that starts with the graph and works ādownā towards the spanning tree and to find a proof that starts with just the vertices and works āupā towards the spanning tree. Can you find both kinds of proof?

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.

Describe a method (or better, two methods different in at least one aspect) for finding a spanning tree of minimum cost in a graph whose edges are labeled with costs, the cost on an edge being the cost for including that edge in a spanning tree. Prove that your method(s) work.

Hint 1
Hint 2

Think of selecting one edge of the tree at a time. Given that you have chosen some edges and have a graph whose connected components are trees, what is a good way to choose the next edge? To prove your method correct, use contradiction by assuming there is a spanning tree tree with lower total cost.

Think of selecting one edge of the tree at a time. But now do it in such a way that one connected component is a tree and the other connected components have just one vertex. What is a good way to make the component that is a tree into a tree with one more vertex? To prove your method works, use contradiction by assuming there is a spanning tree with lower total cost.

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.

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:

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

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

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

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

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?

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.

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

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

Show that the following algorithm (known as Dijkstra's algorithm) applied to a weighted graph whose vertices are labeled 1 to \(n\) gives, for each \(i\text{,}\) the distance from vertex 1 to i as \(d(i)\text{.}\)

Let \(d(1) = 0\text{.}\) Let \(d(i) = \infty\) for all other \(i\text{.}\) Let \(v(1)\)=1. Let \(v(j) = 0\) for all other \(j\text{.}\) For each \(i\) and \(j\text{,}\) let \(w(i,j)\) be the minimum weight of an edge between \(i\) and \(j\text{,}\) or \(\infty\) if there are no such edges. Let \(k=1\text{.}\) Let \(t=1\text{.}\)

For each \(i\text{,}\) if \(d(i)>d(k) + w(k,i)\) let \(d(i)= d(k) +w(k,i)\text{.}\)

Among those \(i\) with \(v(i)=0\text{,}\) choose one with \(d(i)\) a minimum, and let \(k=i\text{.}\) Increase \(t\) by 1. Let \(v(i) =1.\)

Repeat the previous two steps until \(t=n\)

Is there a spanning tree such that the distance from vertex \(1\) to vertex \(i\) given by the algorithm in ProblemĀ 120 is the distance for vertex 1 to vertex \(i\) in the tree (using the same weights on the edges, of course)?