# Extra pearls in graph theory

Anton Petrunin

I used these topics together with ‘‘Pearls in graph theory’’ by Nora
Hartsfield and Gerhard Ringel [18] to teach an undergraduate course in graph
theory at the Pennsylvania State University. I tried to keep clarity and
simplicity on the same level.

Hope that someone will find it useful for something.

I want to thank Semyon Alesker, Rostislav Matveyev, Alexei Novikov, Dmitri
Panov, and Lukeria Petrunina for help.

Anton Petrunin

This work is licensed under the Creative Commons Attribution-ShareAlike 4.0
International License. To view a copy of this license, visit
http://creativecommons.org/licenses/by-sa/4.0/

###### Contents

  1. 1 Introduction
  2. 2 Probabilistic method
  3. 3 Deletion and contraction
  4. 4 Matrix theorem
  5. 5 Graph-polynomials
  6. 6 Generating functions
  7. 7 Minimum spanning trees
  8. 8 Marriage theorem and its relatives
  9. 9 Toroidal graphs
  10. 10 Rado graph
  11. A Corrections and additions

##  Chapter 1 Introduction

### Terminology

$a$$b$$c$$d$

The diagram on the right may describe regular flights of an airline. It has
six flights which serve four airports labeled by $a$, $b$, $c$, and $d$.

For this and similar type of data, mathematicians use the notion of
_pseudograph_.

Formally, a pseudograph is a finite nonempty set of _vertexes_ (in our example
a vertex is an airport) and a finite collection of _edges_ ; each edge
connects two vertexes (in the example above, an edge is a regular flight). A
pair of vertexes can be connected by a few edges, such edges are called
_parallel_ (in our example, it might mean that the airline makes few flights a
day between these airports). Also, an edge can connect a vertex to itself,
such an edge is called a _loop_ (we might think of it as a sightseeing
flight).

Thus, from a mathematical point of view, the diagram above describes an
example of a pseudograph with vertexes $a$, $b$, $c$, $d$, and six edges,
among them is one loop at $c$ and a pair of parallel edges between $b$ and
$d$.

The number of edges coming from one vertex is called its _degree_ , the loops
are counted twice. In the example above, the degrees of $a,b,c,$ and $d$ are
$1,4,4,$ and $3$ correspondingly.

A vertex with zero degree is called _isolated_ and a vertex of degree one is
called an _end vertex_.

A pseudograph without loops is also called a _multigraph_. A multigraph
without parallel edges is also called a _graph_. Most of the time we will work
with graphs.

If $x$ and $y$ are vertexes of a pseudograph $G$, we say that $x$ is
_adjacent_ to $y$ if there is an edge between $x$ and $y$. We say that a
vertex $x$ is _incident_ with an edge $e$ if $x$ is an end vertex of $e$.

### Wolf, goat, and cabbage

Usually we visualize the vertexes of a graph by points and its edges are
represented by a line connecting two vertexes.

However, the vertexes and edges of the graph might have a very different
nature. As an example, let us consider the following classic problem.

1.1. Problem. A farmer purchased a wolf, a goat, and a cabbage; he needs to
cross a river with them. He has a boat, but he can carry only himself and a
single one of his purchases: the wolf, the goat, or the cabbage.

If left unattended together, the wolf would eat the goat, and the goat would
eat the cabbage.

The farmer has to carry himself and his purchases to the far bank of the
river, leaving each purchase intact. How can he do it?

Solution. Let us denote the farmer by $*$, the river by ${\parallel}$ the wolf
by $w$, the goat by $g$, and the cabbage by $c$. For example,
$wc{\parallel}{*}g$ means that the wolf and cabbage are on the left bank of
the river and the goat with the farmer are on the right bank.

The starting position is $wgc{*}{\parallel}$; that is, everyone is on the left
bank. The following graph describes all possible positions which can be
achieved; each edge is labeled by the transported purchase.

${wgc{*}}{\parallel}{}$${wc}{\parallel}{{*}g}$${wc{*}}{\parallel}{g}$${w}{\parallel}{{*}gc}$${c}{\parallel}{{*}gw}$${cg{*}}{\parallel}{w}$${wg{*}}{\parallel}{c}$${g}{\parallel}{{*}wc}$${g{*}}{\parallel}{wc}$${}{\parallel}{{*}wgc}$$g$$c$$w$$g$$g$$w$$c$$g$

This graph shows that the farmer can achieve ${}{\parallel}{{*}wgc}$ by legal
moves. It solves the problem, and also shows that there are exactly two
different solutions, assuming that the farmer does not want to repeat the same
position twice. ∎

Often, a graph comes with an extra structure; for example, labeling of edges
and/or vertexes as in the example above.

Here is a small variation of another classic problem.

1.2. Problem. Missionaries and cannibals must cross a river using a boat which
can carry at most two people, under the constraint that, for both banks, if
there are missionaries present on the bank, they cannot be outnumbered by
cannibals; otherwise the missionaries will be eaten. The boat cannot cross the
river by itself with no people on board.

Let us introduce a notation to describe the positions of the missionaries,
cannibals, and the boat on the banks. The river will be denoted by
${\parallel}$; let $*$ denotes the boat, we will write the number of cannibals
on each side of ${\parallel}$, and the number of missionaries by subscript.
For example, $4_{2}^{*}{\parallel}0_{2}$ means that on the left bank we have
four cannibals, two missionaries, and the boat (these two missionaries will be
eaten), and on the right bank there are no cannibals and two missionaries.

1.3. Exercise. Assume four missionaries and four cannibals need to cross the
river; in other words, the beginning stage is $4_{4}^{*}{\parallel}0_{0}$.
Draw a graph for all possible positions which can be achieved.

Conclude that all of them can not cross the river.

##  Chapter 2 Probabilistic method

In this chapter we give a general discussion of Ramsey numbers, introduce the
probabilistic method, and use it to give a lower bound on Ramsey number.

### Ramsey numbers

Recall that the Ramsey number $r(m,n)$ is a least positive integer such that
every blue-red coloring of edges in the complete graph $K_{r(m,n)}$ contains a
blue $K_{m}$ or a red $K_{n}$.

Switching colors in the definition shows that $r(m,n)=r(n,m)$ for any $m$ and
$n$. Therefore we may assume that $m\leqslant n$.

Note that $r(1,n)=1$ for any positive integer $n$. Indeed, the one-vertex
graph $K_{1}$ has no edges; therefore we can say that all its edges are blue
(as well as red and _deep green-cyan turquoise_ at the same time).

2.1. Exercise. Show that $r(2,n)=n$ for any positive integer $n$.

The following table from [30] gives the values of $r(m,n)$; it includes all
currently known values for $n\geqslant m\geqslant 3$:

$\\!\\!m$ $n\\!\\!$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
---|---|---|---|---|---|---|---|---|---
1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1
2 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
3 | 1 | 3 | 6 | 9 | 14 | 18 | 23 | 28 | 36
4 | 1 | 4 | 9 | 18 | 25 | ? | ? | ? | ?

In order to prove that $r(4,4)=18$ we have to prove two inequalities
$r(4,4)\geqslant\nobreak 18$ and $r(4,4)\leqslant\nobreak 18$. The inequality
$r(4,4)\geqslant\nobreak 18$ means that there is a blue-red coloring of edges
of $K_{17}$ that has no monochromatic $K_{4}$. The inequality $r(4,4)\leqslant
18$ means that in any blue-red coloring of $K_{18}$ there is a monochromatic
$K_{4}$.

### Binomial coefficients

In this section we review properties of binomial coefficients that will be
needed further.

_Binomial coefficients_ will be denoted by $\tbinom{n}{m}$. They can be
defined as unique numbers such that the identity

$(a+b)^{n}=\tbinom{n}{0}{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}a^{0}{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}b^{n}+\tbinom{n}{1}{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}a^{1}{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}b^{n-1}+\dots+\tbinom{n}{n}{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}a^{n}{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}b^{0}$ ➊

holds for any real numbers $a,b$ and integer $n\geqslant 0$. This identity is
called _binomial expansion_. It can be used to derive some identities on
binomial coefficients; for example,

$\tbinom{n}{0}+\tbinom{n}{1}+\dots+\tbinom{n}{n}=(1+1)^{n}=2^{n}.$ ➋

The number $\tbinom{n}{m}$ plays an important role in combinatorics — it gives
the number of ways that $m$ objects can be chosen from $n$ different objects;
this value can be found explicitly:

$\tbinom{n}{m}=\frac{n!}{m!{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}(n-m)!}.$

Note that all $\tbinom{n}{m}$ different ways to choose $m$ objects from $n$
different objects are falling into two categories: (1) those which include the
last object — there are $\tbinom{n-1}{m-1}$ of them, and (2) those which do
not include it — there are $\tbinom{n-1}{m}$ of them. It follows that

$\tbinom{n}{m}=\tbinom{n-1}{m-1}+\tbinom{n-1}{m}.$ ➌

This identity will be used in the proof of Theorem 2.

### Upper bound

Recall that according to Theorem 4.3.2 in [18], the inequality

$r(m,n)\leqslant r(m-1,n)+r(m,n-1)$ ➍

holds for all integers $m,n\geqslant 2$.

In other words, any value $r(m,n)$ in the table above can not exceed the sum
of values in the cells directly above and on the left from it. The inequality
➍ ‣ 2 might be strict; for example,

$r(3,4)=9<4+6=r(2,4)+r(3,3).$

2.2. Theorem. For any positive integers $m,n$ we have that

$r(m,n)\leqslant\tbinom{m+n-2}{m-1}.$

Proof. Set

$s(m,n)=\tbinom{m+n-2}{m-1}=\tfrac{(m+n-2)!}{(m-1)!{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}(n-1)!},$

so we need to prove the following inequality:

$r(m,n)\leqslant s(m,n).$ ➎

Note that from ➌ ‣ 2, we get the identity

$s(m,n)=s(m-1,n)+s(m,n-1)$ ➏

which is similar to the inequality ➍ ‣ 2.

Further note that $s(1,n)=s(n,1)=1$ for any positive integer $n$. Indeed,
$s(1,n)=\tbinom{n-1}{0}$, and there is only one choice of $0$ objects from the
given $n-1$. Similarly $s(n,1)=\tbinom{n-1}{n-1}$, and there is only one
choice of $n-1$ objects from the given $n-1$.

The above observations make it possible to calculate the values of $s(m,n)$
recursively. The following table provides some of its

$\\!\\!m$ $n\\!\\!$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
---|---|---|---|---|---|---|---|---|---
1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1
2 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
3 | 1 | 3 | 6 | 10 | 15 | 21 | 28 | 36 | 45
4 | 1 | 4 | 10 | 20 | 35 | 56 | 84 | 120 | 165

values. The inequality ➎ ‣ 2 means that any value in this table can not exceed
the corresponding value in the table for $r(m,n)$ on page 2. The latter is
nearly evident from ➍ ‣ 2 and ➏ ‣ 2; let us show it formally.

Since

$r(1,n)=r(n,1)=s(1,n)=s(n,1)=1,$

the inequality ➎ ‣ 2 holds if $m=1$ or $n=1$.

Assume the inequality ➎ ‣ 2 does not hold for some $m$ and $n$. Choose a
_minimal criminal_ pair $(m,n)$; that is, a pair with minimal value $m+n$ such
that ➎ ‣ 2 does not hold. From above we have that $m,n\geqslant 2$. Since
$m+n$ is minimal, we have that

$r(m-1,n)\leqslant s(m-1,n)\quad\text{and}\quad r(m,n-1)\leqslant s(m,n-1)$

summing these two inequalities and applying ➍ ‣ 2 together with ➏ ‣ 2 we get ➎
‣ 2 — a contradiction. ∎

2.3. Corollary. The inequality

$r(n,n)\leqslant\tfrac{1}{4}{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}4^{n}$

holds for any positive integer $n$.

Proof. By ➋ ‣ 2, we have that $\tbinom{k}{m}\leqslant 2^{k}$. Applying Theorem
2, we get that

$\displaystyle r(n,n)$ $\displaystyle\leqslant\tbinom{2{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}n-2}{n-1}\leqslant$ $\displaystyle\leqslant
2^{2{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}n-2}=$
$\displaystyle=\tfrac{1}{4}{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}4^{n}.$

∎

### Lower bound

In order to show that

$r(m,n)\geqslant s+1,$

it is sufficient to color the edges of $K_{s}$ in red and blue so that it has
no red $K_{m}$ and no blue $K_{n}$. Equivalently, it is sufficient to
decompose $K_{s}$ into two subgraphs with no isomorphic copies of $K_{m}$ in
the first one and no isomorphic copies of $K_{n}$ in the second one.

For example, the subgraphs in the decomposition of $K_{5}$ on the diagram has
no monochromatic triangles; the latter implies that $r(3,3)\geqslant 6$. We
already showed that for any decomposition of $K_{6}$ into two subgraphs, one
of the subgraphs has a triangle; that is, $r(3,3)=6$.

Similarly, to show that $r(3,4)\geqslant 9$, we need to construct a
decomposition of $K_{8}$ into two subgraphs $G$ and $H$ such that $G$ contains
no triangle $K_{3}$ and $H$ contains no $K_{4}$. In fact, in any decomposition
of $K_{9}$ into two subgraphs, either the first subgraph contains a triangle
or the second contains a $K_{4}$. That is, $r(3,4)=9$ [[, see]p.
82–83]hartsfield-ringel.

Further, to show that $r(4,4)\geqslant 18$, we need to construct a
decomposition of $K_{17}$ into two subgraphs with no $K_{4}$. (In fact,
$r(4,4)=18$, but we are not going to prove it.) The corresponding
decomposition is given on the diagram. The constructed decomposition is
rationally symmetric; the first subgraph contains the chords of angle lengths
1, 2, 4, and 8 and the second contains all the chords of angle lengths 3, 5,
6, and 7.

2.4. Exercise. Show that

  1. (a)

In the decomposition of $K_{8}$ above, the left graph contains no triangle,
and the right graph contains no $K_{4}$.

  2. (b)

In the decomposition of $K_{17}$, neither graph contains any $K_{4}$.

Hint: Assuming such a subgraph exists. Fix a vertex $v$. Note that we can
assume that the subgraph contains $v$; otherwise rotate it. In each case, draw
the subgraph induced by the vertexes connected to $v$. (If uncertain, see the
definition of _induced subgraph_.)

For larger values $m$ and $n$, the problem of finding the exact lower bound
for $r(m,n)$ quickly becomes too hard. Even getting a reasonable estimate is
challenging. In the next section we will show how to obtain such an estimate
by using probability.

### Probabilistic method

The probabilistic method makes it possible to prove the existence of graphs
with certain properties without constructing them explicitly. The idea is to
show that if one randomly chooses a graph or its coloring from a specified
class, then the probability that the result is of the needed property is more
than zero. The latter implies that a graph with needed property exists.

Despite that this method of proof uses probability, the final conclusion is
determined for certain, without any possible error.

2.5. Theorem. Assume that the inequality

$\tbinom{R}{n}<2^{{\binom{n}{2}}-1}$

holds for a pair of positive integers $R$ and $n$. Then $r(n,n)>R$.

Proof. We need to show that the complete graph $K_{R}$ admits a coloring of
edges in red and blue such that it has no monochromatic subgraph isomorphic to
$K_{n}$.

Let us color the edges randomly — color each edge independently with
probability $\tfrac{1}{2}$ in red and otherwise in blue.

Fix a set $S$ of $n$ vertexes. Define the variable $X(S)$ to be $1$ if every
edge between the vertexes in $S$ has the same color, and otherwise set
$X(S)=0$. Note that the number of monochromatic $n$-subgraphs in $K_{R}$ is
the sum of $X(S)$ over all possible $n$-vertex subsets $S$.

Note that the expected value of $X(S)$ is simply the probability that all of
the $\tbinom{n}{2}=\tfrac{n{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}(n-1)}{2}$
edges in $S$ are the same color. The probability that all the edges with the
ends in $S$ are blue is ${2^{-\binom{n}{2}}}$ and with the same probability
all the edges are red. Since these two possibilities exclude each other, the
expected value of $X(S)$ is ${2}{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}{2^{-\binom{n}{2}}}.$

This holds for any $n$-vertex subset $S$ of the vertexes of $K_{R}$. The total
number of such subsets is $\tbinom{R}{n}$. Therefore the expected value for
the sum of $X(S)$ over all $n$-vertex subsets $S$ is

$W=2{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}\tbinom{R}{n}{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}2^{-\binom{n}{2}}.$

In other words, $W$ is the expected number of monochromatic $K_{n}$’s in a
random coloring of $K_{R}$. For any coloring, this number has to be an
integer. Therefore, if $W<1$, then at least one edge-coloring of $K_{R}$ has
no monochromatic $K_{n}$. That is, if $\tbinom{R}{n}<2^{\binom{n}{2}-1},$ then
there is a coloring $K_{R}$ without any monochromatic $n$-subgraphs. ∎

The following corollary implies that the function $n\mapsto r(n,n)$ grows at
least exponentially.

2.6. Corollary. $r(n,n)>\tfrac{1}{8}{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}2^{\frac{n}{2}}$.

Proof. Set $R=\lfloor\tfrac{1}{8}{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}2^{\frac{n}{2}}\rfloor$; that is, $R$ is the largest integer
$\leqslant\tfrac{1}{8}{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}2^{\frac{n}{2}}$.

Note that

$2^{\binom{n}{2}-1}>(2^{\frac{n-3}{2}})^{n}\geqslant R^{n}.$

and

$\tbinom{R}{n}=\frac{R{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}(R-1)\cdots(R-n+1)}{n!}<R^{n}.$

Therefore

$\tbinom{R}{n}<2^{\binom{n}{2}-1}.$

By Theorem 2, we get that $r(n,n)>R$. ∎

2.7. Exercise. By random coloring we understand a coloring of edges of a given
graph in red and blue such that each edge is colored independently in red or
blue with equal chances.

Assume the edges of the complete graph $K_{100}$ is colored randomly. Find the
expected number of monochromatic Hamiltonian cycles in $K_{100}$. (You may use
factorials in the answer.)

Remark. The answer in the exercise above is a huge number that is bigger than
$10^{125}$. One might think that this estimate alone is sufficient to conclude
that _most_ of the colorings have a monochromatic Hamiltonian cycles — let us
show that it is not that easy. (It is still true that probability of the
existence of a monochromatic coloring is close to 1, but the proof requires
more work; it does not follow solely from the given estimate.)

The total number of colorings of $K_{100}$ is $2^{\binom{100}{2}}>10^{1400}$.
Therefore in principle, it might happen that $99.99\%$ of the colorings have
no monochromatic Hamiltonian cycles and $.01\%$ of the colorings contain all
the monochromatic Hamiltonian cycles. To keep the expected value above
$10^{125}$, this $.01\%$ of colorings should have less than $10^{130}$ of
monochromatic cycles in average; the latter does not seem impossible since the
total number of Hamiltonian cycles in $K_{100}$ is $99!/2>10^{155}$.

### Counting proof

In this section, we translate the proof of Theorem 2 into a combinatoric
language, without the use of probability. We do this to affirm that the
probabilistic method provides a real proof, without any possible error.

In principle, any probabilistic proof admits such a translation, but in most
cases, the translation is less intuitive.

Proof of 2. The graph $K_{R}$ has $\tbinom{R}{2}$ edges. Each edge can be
colored in blue or red; therefore the total number of different colorings is

$\Omega=2^{\binom{R}{2}}.$

Fix a subgraph isomorphic to $K_{n}$ in $K_{R}$. Note that this graph is red
in $\Omega/2^{\binom{n}{2}}$ different colorings and yet in
$\Omega/2^{\binom{n}{2}}$ different colorings this subgraph is blue.

There are $\tbinom{R}{n}$ different subgraphs isomorphic to $K_{n}$ in
$K_{R}$. Therefore the total number of monochromatic $K_{n}$’s in all the
colorings is

$M=\tbinom{R}{n}{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}\Omega{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}2/2^{\binom{n}{2}}.$

If $M<\Omega$, then by the pigeonhole principle, there is a coloring with no
monochromatic $K_{n}$. Hence the result. ∎

### Graph of $\bm{n}$-cube

In this section we give another classic application of the probabilistic
method. It requires a bit more probability theory.

Let us denote by $Q_{n}$ the graph of the $n$-dimensional cube; $Q_{n}$ has
$2^{n}$ vertexes, each vertex is labeled by a sequence of length $n$ made up
of zeros and ones; two vertexes are adjacent if their labels differ only in
one digit.

Graph $Q_{4}$ is shown on the diagram. Note that each vertex of $Q_{n}$ has
degree $n$.

Recall that _distance_ between two vertexes in a graph $G$ is the length of a
shortest path connecting the vertexes. The maximal distance between vertexes
in $G$ is called _diameter_ of $G$.

2.8. Exercise. Show that the diameter of $Q_{n}$ is $n$.

2.9. Problem. Suppose $\ell(n)$ denotes the maximal number of vertexes in
$Q_{n}$ on a distance more than $n/3$ from each other. Then $\ell(n)$ grows
exponentially in $n$; moreover, $\ell(n)\geqslant 1.05^{n}$.

To solve the problem one has to construct a set with at least $1.05^{n}$
vertexes in $Q_{n}$ that lie far from each other. However, it is hard to
construct such a set explicitly. Instead, we will show that if one chooses
that many vertexes randomly, then they lie far from each other with a positive
probability. To choose a random vertex in $Q_{n}$, one can toss a coin $n$
times, each time writing 1 for a head and 0 for a tail and then take the
vertex labeled by the obtained sequence.

The following exercise guides you to a solution of the problem. The same
argument shows that for any coefficient $k<\tfrac{1}{2}$, the maximal number
of vertexes in $Q_{n}$ on the distance larger than $k{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}n$ from each other grows exponentially in $n$.
According to Exercise 2, the case $k=\tfrac{1}{2}$ is very different.

2.10. Exercise. Let $P_{n}$ denote the probability that randomly chosen
vertexes in $Q_{n}$ lie with the distance $\leqslant\tfrac{n}{3}$ between
them.

  1. (a)

Use Claim 2 to show that

$P_{n}<.95^{n}.$

  2. (b)

Assume $k$ vertexes $v_{1},\dots,v_{k}$ in $Q_{n}$ are fixed and $v$ is a
random vertex. Show that $k{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}P_{n}$ is
the average number of vertexes $v_{i}$ that lies on a distance
$\leqslant\tfrac{n}{3}$ from $v$. Conclude that $v$ lies on a distance larger
than $\tfrac{n}{3}$ from each of $v_{i}$ with probability at least $1-k{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}P_{n}$.

  3. (c)

Apply a and b to show that there are at least $1.05^{n}$ vertexes in $Q_{n}$
on a distance larger than $\tfrac{n}{3}$ from each other.

2.11. Claim. The probability $P_{n}$ to obtain less than one third heads after
$n$ fair tosses of a coin decays exponentially in $n$; in fact $P_{n}<.95^{n}$
for any $n$.

In the proof, we will use the following observation.

2.12. Markov’s inequality. Suppose $Y$ is a nonnegative random variable and
$c>0$. Denote by $P$ the probability of the event $Y\geqslant c$ and by $y$
the expected value of $Y$. Then

$P{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}c\leqslant y.$ ➐

Proof. Consider another random variable $\bar{Y}$ such that $\bar{Y}=c$ if
$Y\geqslant c$ and $\bar{Y}=0$ otherwise; denote by $\bar{y}$ its expected
value.

Note that $\bar{Y}\leqslant\nobreak Y$ and therefore

$\bar{y}\leqslant y.$

The random variable $\bar{Y}$ takes the value $c$ with probability $P$ and $0$
with probability $1-P$. Therefore $\bar{y}=P{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}c$; whence ➐ ‣ 2 follows. ∎

Proof of 2. Let us introduce independent $n$ random variables
$X_{1},\dots\nobreak X_{n}$; each $X_{i}$ returns the number of heads after
$i$-th toss of the coin; in particular, each $X_{i}$ takes values $0$ or $1$
with the probability of $\tfrac{1}{2}$ each. We need to show that the
probability $P_{n}$ of the event $X_{1}+\dots+X_{n}\leqslant\tfrac{n}{3}$ is
less than $.95^{n}$.

Consider the random variable

$Y=2^{-X_{1}-\dots-X_{n}};$

denote by $y$ its expected value.

Note that $P_{n}$ is the probability of the event that $Y\geqslant
2^{-\frac{n}{3}}$. Further note that $Y>0$ always. By Markov’s inequality, we
get that

$P_{n}{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}2^{-\frac{n}{3}}\leqslant y.$

The random variable $2^{-X_{i}}$ takes the two values $1$ and
$\tfrac{1}{2}=2^{-1}$ with the probability of $\tfrac{1}{2}$ each; the
expected value of $2^{-X_{i}}$ has to be $\tfrac{1}{2}{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}(1+\tfrac{1}{2})=\tfrac{3}{4}$. Note that

$Y=2^{-X_{1}}\cdots 2^{-X_{n}}.$

Since the random variables $X_{i}$ are independent, we have that

$y=\left(\tfrac{3}{4}\right)^{n}.$

It follows that

$P_{n}\leqslant\left(\tfrac{3}{4}{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}2^{\frac{1}{3}}\right)^{n}<.95^{n}.$

∎

2.13. Advanced exercise.

  1. (a)

Show that $Q_{n}$ contains at most $2{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}n$
vertexes on a distance at least $\tfrac{n}{2}$ from each other.

  2. (b)

Show that $Q_{n}$ contains at most $n+1$ vertexes on a distance larger than
$\tfrac{n}{2}$ from each other.

### Remarks

Existence of Ramsey number $r(m,n)$ for any $m$ and $n$, is the first result
in the so called _Ramsey theory_. A typical theorem in this theory states that
any large object of a certain type contains a very ordered piece of a given
size. We recommend a book of Matthew Katz and Jan Reimann [24] on the subject.

Corollaries 2 and 2 imply that

$\tfrac{1}{8}{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}2^{\frac{1}{2}{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}n}\leqslant r(n,n)\leqslant\tfrac{1}{4}{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}2^{2{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}n}.$

It is unknown if these inequalities can be essentially improved.111This
question might look insignificant from the first sight, but it is considered
as one of the major problems in combinatorics [14]. More precisely, it is
unknown whether there are constants $c>0$ and $\alpha>\tfrac{1}{2}$ such that
the inequality

$r(n,n)\geqslant c{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}2^{\alpha{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}n}$

holds for any $n$. Similarly, it is unknown whether there are constants $c$
and $\alpha<2$ such that the inequality

$r(n,n)\leqslant c{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}2^{\alpha{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}n}$

holds for any $n$.

The probabilistic method was introduced by Paul Erdős. It finds applications
in many areas of mathematics, not only in graph theory.

Note that the probabilistic method is nonconstructive — often when the
existence of a certain graph is probed by the probabilistic method, it is
still uncontrollably hard to describe a concrete example.

More involved examples of proofs based on the probabilistic method deal with
_typical properties_ of random graphs.

To describe the concept, let us consider the following _random process_ which
generates a graph $G_{n}$ with $n$ vertexes.

Fix a positive integer $n$. Consider a graph $G_{n}$ with the vertexes labeled
by $1,\dots,n$, where existence of edge between every pair of vertexes is
decided independently by flipping a coin.

Note that the described process depends only on $n$, and as a result we can
get a graph isomorphic to any given graph with $n$ vertexes.

2.14. Exercise. Let $H$ be a graph with $n$ vertexes. Denote by $\alpha$ the
probability that $G_{n}$ is isomorphic to $H$. Show that

$1/2^{\binom{n}{2}}\leqslant\alpha\leqslant n!/2^{\binom{n}{2}}.$

Fix a property of a graph (for example, connectedness) and denote by
$\alpha_{n}$ the probability that $G_{n}$ has this property. We say that the
property is _typical_ if $\alpha_{n}\to 1$ as $n\to\infty$.

2.15. Exercise. Show that random graphs typically have a diameter of 2. That
is, the probability that $G_{n}$ is has a diameter of 2 converges to 1 as
$n\to\infty$.

Hint: Find the probability that two given vertexes lie on a distance $>2$ from
each other in $G_{n}$; find the average number of such pairs in $G_{n}$; make
a conclusion.

Note that from the exercise above, it follows that in the described random
process, the random graphs are _typically connected_.

2.16. Exercise. Show that random graphs typically has a subgraph isomorphic to
$K_{100}$. That is, the probability that $G_{n}$ has a subgraph isomorphic to
$K_{100}$ converges to 1 as $n\to\infty$.

The following theorem gives a deeper illustration of the probabilistic method
with the use of typical properties, a proof can be found in [1, Chapter 44].

2.17. Theorem. Given positive integers $g$ and $k$, there is a graph $G$ with
girth of at least $g$ and a chromatic number of at least $k$.

##  Chapter 3 Deletion and contraction

### Definitions

Let $G$ be a pseudograph with a marked edge $e$. Denote by $G-e$ the
pseudograph obtained from $G$ by deleting $e$, and by $G/e$ the pseudograph
obtained from $G$ by contracting the edge $e$ to a point; see the diagram.

Assume $G$ is a graph; that is, $G$ has no loops and no parallel edges. In
this case, $G-e$ is also a graph. However, $G/e$ might have parallel edges,
but no loops; that is, $G/e$ is a multigraph.

If $G$ is a multigraph, then so is $G-e$. If the edge $e$ is parallel to $f$
in $G$, then $f$ in $G/e$ becomes a loop; that is, $G/e$ is a pseudograph in
general.

### Number of spanning trees

Recall that $s(G)$ denotes the number of spanning trees in the pseudograph
$G$.

An edge $e$ in a connected graph $G$ is called the _bridge_ , if deletion of
$e$ makes the graph disconnected; in this case, the remaining graph has two
connected components which are called _banks_.

3.1. Exercise. Assume that the graph $G$ contains a bridge between banks
$H_{1}$ and $H_{2}$. Show that

$s(G)=s(H_{1}){\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}s(H_{2}).$

3.2. Deletion-plus-contraction formula. Let $e$ be an edge in the pseudograph
$G$. Assume $e$ is not a loop, then the following identity holds

$s(G)=s(G-e)+s(G/e).$ ➊

It is convenient to write the identity ➊ ‣ 3 using a diagram as on the picture
— the arrows point from one multigraph to multigraphs with the same total
number of spanning trees; the edge $e$ is marked in $G$.

Proof. Note that the spanning trees of $G$ can be subdivided into two groups —
(1) those which contain the edge $e$ and (2) those which do not. For the trees
in the first group, the contraction of $e$ to a point gives a spanning tree in
$G/e$, while the trees in the second group are also spanning trees in $G-e$.

Moreover, both of the described correspondences are one-to-one. Hence the
formula follows. ∎

Note that a spanning tree can not have loops. Therefore if we remove all loops
from the pseudograph, the number of spanning trees remains unchanged. Let us
state it precisely.

3.3. Claim. If $e$ is a loop in a pseudograph $G$, then

$s(G)=s(G-e).$

The proof of the following claim uses the deletion-plus-contraction formula.

3.4. Claim. If one removes an end vertex $w$ from a pseudograph $G$, then in
the obtained graph $G-w$ the number of spanning trees remains unchanged; that
is,

$s(G)=s(G-w).$ ➋

Proof. Denote by $e$ the only edge incident to $w$. Note that the graph $G-e$
is not connected, since the vertex $w$ is isolated. In particular, $s(G-e)=0$.
On the other hand, $G/e=G-w$. Therefore the deletion-plus-contraction formula
➊ ‣ 3 implies ➋ ‣ 3. ∎

On the diagrams, we may use two-sided arrow ‘‘$\leftrightarrow$’’ for the
graphs with equal number of the spanning trees. For example, using deletion-
plus-contraction formula together with the claims, we can draw the diagram,
which in particular implies the following identity:

$s(G)=2{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}s(H).$

Note that the deletion-plus-contraction formula gives an algorithm to
calculate the value $s(G)$ for a given pseudograph $G$. Indeed, for any edge
$e$, both graphs $G-e$ and $G/e$ have smaller number of edges. That is, the
deletion-plus-contraction formula reduces the problem of finding the number of
the trees to simpler graphs; applying this formula a few times we can reduce
the question to a collection of graphs with an evident answer for each. In the
next section we will show how it works.

### Fans and their relatives

Recall that _Fibonacci numbers_ $f_{n}$ are defined using the recursive
identity $f_{n+1}=f_{n}+f_{n-1}$ with $f_{1}=f_{2}=1$. The sequence of
Fibonacci numbers starts as

$1,1,2,3,5,8,13,\dots$

The graphs of the following type are called _fans_ ;

a fan with $n+1$ vertex will be denoted by $F_{n}$.

3.5. Theorem. $s(F_{n})=f_{2{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}n}$.

Proof. Applying the deletion-plus-contraction formula, we can draw the
following infinite diagram.

(We ignore loops and end vertexes since they do not change the number of
spanning trees.) In addition to the fans $F_{n}$ we use its variations
$F_{n}^{\prime}$, which differ from $F_{n}$ by an extra parallel edge.

Set $a_{n}=s(F_{n})$ and $a^{\prime}_{n}=s(F^{\prime}_{n})$. From the diagram,
we get the following two recursive relations:

$\displaystyle a_{n+1}$ $\displaystyle=a^{\prime}_{n}+a_{n},$ $\displaystyle
a^{\prime}_{n}$ $\displaystyle=a_{n}+a^{\prime}_{n-1}.$

That is, in the sequence

$a_{1},a_{1}^{\prime},a_{2},a_{2}^{\prime},a_{3}\dots$

every number starting from $a_{2}$ is sum of previous two.

Further note that $F_{1}$ has two vertexes connected by a unique edge, and
$F^{\prime}_{1}$ has two vertexes connected by a pair of parallel edges. Hence
$a_{1}=1=f_{2}$ and $a_{1}^{\prime}=2=f_{3}$ and therefore

$a_{n}=f_{2{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}n}$

for any $n$.∎

Comments. We can deduce a recursive relation for $a_{n}$, without using
$a_{n}^{\prime}$:

$\displaystyle a_{n+1}$ $\displaystyle=a_{n}^{\prime}+a_{n}=$
$\displaystyle=2{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}a_{n}+a^{\prime}_{n-1}=$ $\displaystyle=3{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}a_{n}-a_{n-1}.$

This is a special case of the so called _constant-recursive sequences_. The
general term of constant-recursive sequences can be expressed by a closed
formula — read [20] if you wonder how. In our case it is

$a_{n}=\tfrac{1}{\sqrt{5}}{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}\left((\tfrac{3+\sqrt{5}}{2})^{n}-(\tfrac{3-\sqrt{5}}{2})^{n}\right).$

Since $a_{n}$ is an integer and $0<\tfrac{1}{\sqrt{5}}{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}(\tfrac{3-\sqrt{5}}{2})^{n}<1$ for any
$n\geqslant 1$, a shorter formula can be written

$a_{n}=\left\lfloor\tfrac{1}{\sqrt{5}}{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}(\tfrac{3+\sqrt{5}}{2})^{n}\right\rfloor,$

where $\lfloor x\rfloor$ denotes floor of $x$; that is, $\lfloor x\rfloor$ is
the maximal integer that does not exceed $x$.

3.6. Exercise. Consider the sequence of zig-zag graphs $Z_{n}$ of the
following type:

Show that $s(Z_{n})=f_{2{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}n}$ for any
$n$.

Hint: Use the induction on $n$ and/or mimic the proof of Theorem 3.

3.7. Exercise. Let us denote by $b_{n}$ the number of spanning trees in the
_$n$ -step ladder_ $L_{n}$; that is, in the graph of the following type:

Apply the method we used for the fans $F_{n}$ to show that the sequence
$b_{n}$ satisfies the following linear recursive relation:

$b_{n+1}=4{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}b_{n}-b_{n-1}.$

Hint: To construct the recursive relation, in addition to the ladders $L_{n}$,
you will need two of its analogs — $L_{n}^{\prime}$ and
$L_{n}^{\prime\prime}$, shown on the diagram.

Note that $b_{1}=1$ and $b_{2}=4$; applying the exercise, we could calculate
the first numbers of the sequence $(b_{n})$:

$1,4,15,56,209,780,2911,\dots$

The following exercise is analogous, but more complicated.

3.8. Advanced exercise. Recall that a wheel $W_{n}$ is the graph of following
type:

Show that the sequence $c_{n}=s(W_{n})$ satisfies the following recursive
relation:

$c_{n+1}=4{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}c_{n}-4{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}c_{n-1}+c_{n-2}.$

Using the exercise above and applying induction, one can show that

$c_{n}=f_{2{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}n+1}+f_{2{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}n-1}-2=l_{2{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}n}-2$

for any $n$. The numbers $l_{n}=f_{n+1}+f_{n-1}$ are called _Lucas numbers_ ;
they pop up in combinatorics as often as Fibonacci numbers.

### Remarks

The _deletion-plus-contraction formula_ together with Kirchhoff’s rules were
used in the solution of the so called _squaring the square problem_. The
history of this problem and its solution are discussed in a book of Martin
Gardiner [12, Chapter 17].

The proof of recurrent relation above is given by Mohammad Hassan Shirdareh
Haghighi and Khodakhast Bibak [34]; this problem is also discussed in a book
of Ronald Graham, Donald Knuth, and Oren Patashnik [15].

##  Chapter 4 Matrix theorem

### Adjacency matrix

Let us describe a way to encode a given multigraph $G$ with $p$ vertexes by an
$p{\times}p$ matrix. First, enumerate the vertexes of the multigraph by
numbers from $1$ to $p$; such a multigraph will be called _labeled_. Consider
the matrix $A=A_{G}$ with the component $a_{i,j}$ equal to the number of edges
from the $i$-th vertex to the $j$-th vertex of $G$.

This matrix $A$ is called the _adjacency matrix_ of $G$. Note that $A$ is
_symmetric_ ; that is, $a_{i,j}=a_{j,i}$ for any pair $i,j$. Also, the
diagonal components of $A$ vanish; that is, $a_{i,i}=0$ for any $i$.

$1$$2$$3$$4$

For example, for the labeled multigraph $G$ shown on the diagram, we get the
following adjacency matrix:

$A=\left(\begin{matrix}0&1&0&1\\\ 1&0&1&2\\\ 0&1&0&0\\\
1&2&0&0\end{matrix}\right).$

4.1. Exercise. Let $A$ be the adjacency matrix of a labeled multigraph. Show
that the components $b_{i,j}$ of the $n$-th power $A^{n}$ is the number of
walks of length $n$ in the graph from vertex $i$ to vertex $j$.

Hint: Use induction on $n$.

### Kirchhoff minor

In this section we construct a special matrix, called _Kirchhoff minor_ ,
associated with a pseudograph, and we discuss its basic properties. This
matrix will be used in the next section in a formula for the number of
spanning trees in a pseudograph $G$. Since the loops do not change the number
of spanning trees, we can remove all of them. In other words, we can (and
will) always assume that $G$ is a multigraph.

Fix a multigraph $G$ and consider its adjacency matrix $A=A_{G}$; it is a
$p{\times}p$ symmetric matrix with zeros on the diagonal.

  1. 1.

Revert the signs of the components of $A$ and exchange the zeros on the
diagonal by the degrees of the corresponding vertexes.

(The matrix $A^{\prime}$ is called the _Kirchhoff matrix_ , _Laplacian matrix_
or _admittance matrix_ of the graph $G$.)

  2. 2.

Delete from $A^{\prime}$ the last column and the last row; the obtained matrix
$M=M_{G}$ will be called the _Kirchhoff minor_ of the labeled pseudograph $G$.

$1$$2$$3$$4$

For example, the labeled multigraph $G$ on the diagram has the following
Kirchhoff matrix and Kirchhoff minor:

$A^{\prime}=\left(\begin{matrix}2&-1&0&-1\\\ -1&4&-1&-2\\\ 0&-1&1&0\\\
-1&-2&0&3\end{matrix}\right),\quad M=\left(\begin{matrix}2&-1&0\\\ -1&4&-1\\\
0&-1&1\end{matrix}\right).$

4.2. Exercise. Show that in any Kirchhoff matrix $A^{\prime}$ the sum of the
components in each row or column vanishes. Conclude that

$\det A^{\prime}=0.$

4.3. Exercise. Draw a labeled pseudograph with following Kirchhoff minor:

$\left(\begin{matrix}4&-1&-1&-1&0\\\ -1&4&-1&0&-1\\\ -1&-1&4&-1&-1\\\
-1&0&-1&4&-1\\\ 0&-1&-1&-1&4\end{matrix}\right).$

4.4. Exercise. Show that the sum of all components in every column of
Kirchhoff minor is nonnegative.

Moreover, the sum of all components in the $i$-th column vanishes if and only
if the $i$-th vertex is not adjacent to the last vertex.

Relabeling. Let us understand what happens with Kirchhoff minor and its
determinant as we swap two labels distinct from the last one.

$1$$3$$2$$4$

For example, if we swap the labels $2$ and $3$ in the graph above, we get
another labeling shown on the diagram. Then the corresponding Kirchhoff minor
will be

$M^{\prime}=\left(\begin{matrix}2&0&-1\\\ 0&1&-1\\\
-1&-1&4\end{matrix}\right),$

which is obtained from $M$ by swapping columns $2$ and $3$ following by
swapping rows $2$ and $3$.

Note that swapping a pair of columns or rows changes the sign of the
determinant. Therefore, swapping one pair of rows and one pair of columns does
not change the determinant. Summarizing we get the following:

4.5. Observation. Assume $G$ is a labeled graph with $p$ vertexes and $M_{G}$
is its Kirchhoff minor. If we swap two labels $i,j<p$, then the corresponding
Kirchhoff minor $M^{\prime}_{G}$ can be obtained from $M_{G}$ by swapping
columns $i$ and $j$, and then swapping rows $i$ and $j$. In particular,

$\det M^{\prime}_{G}=\det M_{G}.$

Deletion and contraction. Let us understand what happens with Kirchhoff minor
if we delete or contract an edge in the labeled multigraph. (If after the
contraction of an edge we get loops, we remove it; this way we obtain a
multigraph.)

Assume an edge $e$ connects the first and the last vertex of a labeled
multigraph $G$ as in the following example:

$1$$2$$3$$4$$e$pt$G$$1$$2$$3$$4$pt$G-e$$2$$3$$4$pt$G/e$

Note that deleting $e$ only reduces the corner component of $M_{G}$ by one,
while contracting it removes the first row and column. That is, since

$M_{G}=\left(\begin{matrix}2&-1&0\\\ -1&4&-1\\\ 0&-1&1\end{matrix}\right),$

we have

$M_{G-e}=\left(\begin{matrix}1&-1&0\\\ -1&4&-1\\\
0&-1&1\end{matrix}\right)\quad\text{and}\quad
M_{G/e}=\left(\begin{matrix}4&-1\\\ -1&1\end{matrix}\right).$

Summarizing the above discussion we get the following:

4.6. Observation. Assume $e$ is an edge of a labeled multigraph $G$ between
the first and last vertex and $M_{G}$ is the Kirchhoff minor of $G$. Then

  1. (a)

the Kirchhoff minor $M_{G-e}$ of $G-e$ can be obtained from $M_{G}$ by
subtracting 1 from the corner element with index (1,1);

  2. (b)

the Kirchhoff minor $M_{G/e}$ of $G/e$ can be obtained from $M_{G}$ by
removing the first row and the first column in $M_{G}$.

In particular, applying the cofactor expansion of a determinant, we get that

$\det M_{G}=\det M_{G-e}+\det M_{G/e}.$

Note that the last formula resembles the deletion-plus-contraction formula.
This observation will be a key to the proof of the matrix theorem; see the
next section.

### Matrix theorem

4.7. Matrix theorem. Let $M$ be the Kirchhoff minor of a labeled multigraph
$G$ with at least two vertexes. Then

$s(G)=\det M,$ ➊

where $s(G)$ denotes the number of spanning trees in $G$.

Proof. Denote by $d$ the degree of the last vertex in $G$.

Assume $d=0$. Then $G$ is not connected and therefore $s(G)=0$. On the other
hand, the sum in each row of $M_{G}$ vanish (compare to Exercise 4). Hence the
sum of all columns in $M_{G}$ vanish; in particular, the columns in $M_{G}$
are linearly dependent and hence $\det M_{G}=0$. Hence the equality ➊ ‣ 4
holds if $d=0$.

As usual, we denote by $p$ and $q$ the number of vertexes and edges in $G$; by
the assumption we have that $p\geqslant 2$.

Assume $p=2$; that is, $G$ has two vertexes and $q$ parallel edges connecting
them. Clearly, $s(G)=q$. Further note that $M_{G}=(q)$; that is, the Kirchhoff
minor $M_{G}$ is a $1{\times}1$ matrix with single component $q$. In
particular, $\det M_{G}=q$ and therefore the equality ➊ ‣ 4 holds.

Assume the equality ➊ ‣ 4 does not hold in general; choose a _minimal criminal
graph_ $G$; that is a graph that minimize the value $p+q$ among the graphs
violating ➊ ‣ 4.

From above we have that $p>2$ and $d>0$. Note that we may assume that the
first and last vertexes of $G$ are adjacent; otherwise permute pair of labels
$1$ and some $j<p$ and apply Observation 4. Denote by $e$ the edge between the
first and last vertex.

Note that the total number of vertexes and edges in the pseudographs $G-e$ and
$G/e$ are smaller than $p+q$. Therefore we have that

$\displaystyle s(G-e)$ $\displaystyle=\det M_{G-e},$ $\displaystyle s(G/e)$
$\displaystyle=\det M_{G/e}.$

Applying these two identities together with the deletion-plus-contraction
formula and Observation 4, we get that

$\displaystyle s(G)$ $\displaystyle=s(G-e)+s(G/e)=$ $\displaystyle=\det
M_{G-e}+\det M_{G/e}=$ $\displaystyle=\det M_{G};$

that is, the identity ➊ ‣ 4 holds for $G$ — a contradiction. ∎

4.8. Exercise. Fix a labeling for each of the following graphs, find its
Kirchhoff minor and use the matrix theorem to find the number of spanning
trees.

  1. (a)

$s(K_{3,3})$;

  2. (b)

$s(W_{6})$;

  3. (c)

$s(Q_{3})$.

(Use _https://matrix.reshish.com/determinant.php_, or any other matrix
calculator.)

### Calculation of determinants

In this section we recall key properties of the determinant which will be used
in the next section.

Let $M$ be an $n{\times}n$-matrix; that is, a table $n{\times}n$, filled with
numbers which are called _components of the matrix_. The determinant $\det M$
is a polynomial of the $n^{2}$ components of $M$, which satisfies the
following conditions:

  1. 1.

The unit matrix has determinant 1; that is,

$\det\left(\begin{matrix}1&0&\cdots&0\\\ 0&1&\ddots&\vdots\\\
\vdots&\ddots&\ddots&0\\\ 0&\cdots&0&1\end{matrix}\right)=1.$

  2. 2.

If we multiply each component of one of the rows of the matrix $M$ multiply by
a number $\lambda$, then for the obtained matrix $M^{\prime}$, we have

$\det M^{\prime}=\lambda{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}\det M.$

  3. 3.

If one of the rows in the matrix $M$ add (or subtract) term-by-term to another
row, then the obtained matrix $M^{\prime}$ has the same determinant

$\det M^{\prime}=\det M.$

These three conditions define determinant in a unique way. We will not give a
proof of the statement; it is not evident and not complicated (sooner or later
you will have to learn it, if it is not done already).

4.9. Exercise. Show that the following property follows from the properties
above.

  1. 4.

Interchanging any pair of rows of a matrix multiplies its determinant by $-1$;
that is, if a matrix $M^{\prime}$ is obtained from a matrix $M$ by permuting
two of its rows, then

$\det M^{\prime}=-\det M.$

The determinant of $n\times n$-matrix can be written explicitly as a sum of
$n!$ terms. For example,

$a_{1}{{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}}b_{2}{{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}}c_{3}+a_{2}{{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}}b_{3}{{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}}c_{1}+a_{3}{{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}}b_{1}{{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}}c_{2}-a_{3}{{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}}b_{2}{{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}}c_{1}-a_{2}{{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}}b_{1}{{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}}c_{3}-a_{1}{{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}}b_{3}{{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}}c_{2}$

is the determinant of the matrix

$M=\left(\begin{matrix}a_{1}&b_{1}&c_{1}\\\ a_{2}&b_{2}&c_{2}\\\
a_{3}&b_{3}&c_{3}\end{matrix}\right).$

However, the properties described above give a more convenient and faster way
to calculate the determinant, especially for larger values $n$.

Let us show it on one example which will be needed in the next section.

$\displaystyle\det\left(\begin{matrix}4&-1&-1&-1\\\ -1&4&-1&-1\\\
-1&-1&4&-1\\\ -1&-1&-1&4\end{matrix}\right)=$
$\displaystyle\det\left(\begin{matrix}1&1&1&1\\\ -1&4&-1&-1\\\ -1&-1&4&-1\\\
-1&-1&-1&4\end{matrix}\right)=$ $\displaystyle=$
$\displaystyle\det\left(\begin{matrix}1&1&1&1\\\ 0&5&0&0\\\ 0&0&5&0\\\
0&0&0&5\end{matrix}\right)=$ $\displaystyle=5^{3}{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}$
$\displaystyle\det\left(\begin{matrix}1&1&1&1\\\ 0&1&0&0\\\ 0&0&1&0\\\
0&0&0&1\end{matrix}\right)=$ $\displaystyle=5^{3}{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}$
$\displaystyle\det\left(\begin{matrix}1&0&0&0\\\ 0&1&0&0\\\ 0&0&1&0\\\
0&0&0&1\end{matrix}\right)=$ $\displaystyle=5^{3}$ .

Let us describe what we used on each line above:

  1. 1.

property 3 three times — we add to the first row each of the remaining rows;

  2. 2.

property 3 three times — we add the first row to the each of the remaining
three rows;

  3. 3.

property 2 three times;

  4. 4.

property 3 three times — we subtract from the first row the remaining three
rows;

  5. 5.

property 1.

### Cayley formula

Recall that a _complete graph_ is a graph where each pair of vertexes is
connected by an edge; a complete graph with $p$ vertexes is denoted by
$K_{p}$.

Note that every vertex of $K_{p}$ has degree $p-1$. Therefore the Kirchhoff
minor $M=M_{K_{p}}$ in the matrix formula ➊ ‣ 4 for $K_{p}$ is the following
$(p-1)\times(p-1)$-matrix:

$M=\left(\begin{matrix}p{-}1&-1&\cdots&-1\\\ -1&p{-}1&\ddots&\vdots\\\
\vdots&\ddots&\ddots&-1\\\ -1&\cdots&-1&p{-}1\end{matrix}\right).$

The argument given in the end of the previous section admits a direct
generalization:

$\displaystyle\det\left(\begin{matrix}p{-}1&-1&\cdots&-1\\\
-1&p{-}1&\ddots&\vdots\\\ \vdots&\ddots&\ddots&-1\\\
-1&\cdots&-1&p{-}1\end{matrix}\right)$
$\displaystyle=\det\left(\begin{matrix}1&1&\cdots&1\\\
-1&p{-}1&\ddots&\vdots\\\ \vdots&\ddots&\ddots&-1\\\
-1&\cdots&-1&p{-}1\end{matrix}\right)=$
$\displaystyle=\det\left(\begin{matrix}1&1&\cdots&1\\\ 0&p&\ddots&\vdots\\\
\vdots&\ddots&\ddots&0\\\ 0&\cdots&0&p\end{matrix}\right)=$
$\displaystyle=p^{p-2}.$

That is,

$\det M=p^{\,p-2}.$

Therefore, applying the matrix theorem, we get the following:

4.10. Cayley formula.

$s(K_{p})=p^{p-2};$

that is, the number of spanning trees in the complete graph $K_{p}$ is
$p^{p-2}$.

4.11. Exercise. Show $s(K_{p}-e)=(p-2){\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}p^{n-3}$ for any edge $e$ in $K_{p}$.

4.12. Exercise. Use the matrix theorem to show that

$s(K_{m,n})=m^{n-1}{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}n^{m-1}.$

### Remarks

There is strong connection between counting spanning trees of a given graph,
calculations of currents in an electric chain and random walks; a good survey
is given in the book of Peter Doyle and Laurie Snell [6]. Let us give some
examples.

Assume that the graph $G$ describes an electric chain; each edge has
resistance one Ohm and a battery is connected to the vertexes $a$ and $b$.
Assume that the total current between these vertexes is one Ampere. The
following procedure calculates the current $I_{e}$ along a given edge $e$.

Fix an orientation of $e$. Note that any spanning tree $T$ of $G$ has exactly
one the following three properties: (1) the edge $e$ appears on the (necessary
unique) path from $a$ to $b$ in $T$ with a positive orientation, (2) the edge
$e$ appears on the path from $a$ to $b$ in $T$ with a negative orientation,
(3) the edge $e$ does not appear on the path from $a$ to $b$ in $T$. Denote by
$s_{+}$, $s_{-}$, and $s_{0}$ the number of the trees in each group. Clearly,

$s(G)=s_{+}+s_{-}+s_{0}.$

Then the current $I_{e}$ can be calculated using the following formula:

$I_{e}=\frac{s_{+}-s_{-}}{s(G)}{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}I.$

This statement can be proved by checking Kirchhoff’s rules for the currents
calculated by this formula.

There are many other applications of Kirchhoff’s rules to graph theory. For
example, in [27], they were used to prove the Euler’s formula

$p-q+r=2,$

where $p$, $q$, and $r$ denote the number of vertexes, edges and regions of in
a plane drawing of graph.

##  Chapter 5 Graph-polynomials

Counting problems often lead to an organized collection of numbers. Sometimes
it is convenient to consider a polynomial with these numbers as coefficients.
If it is done in a smart way, then the algebraic structure of the obtained
polynomial reflects the original combinatorial structure of the graph.

### Chromatic polynomial

Denote by $P_{G}(x)$ the number of different colorings of the graph $G$ in $x$
colors such that the ends of each edge get different colors.

5.1. Exercise. Assume that a graph $G$ has exactly two connected components
$H_{1}$ and $H_{2}$. Show that

$P_{G}(x)=P_{H_{1}}(x){\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}P_{H_{2}}(x)$

for any $x$.

5.2. Exercise. Show that for any integer $n\geqslant 3$,

$P_{W_{n}}(x+1)=(x+1){\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}P_{C_{n}}(x),$

where $W_{n}$ denotes a wheel with $n$ spokes and $C_{n}$ is a cycle of length
$n$.

5.3. Deletion-minus-contraction formula. For any edge $e$ in the pseudograph
$G$ we have

$P_{G}(x)=P_{G-e}(x)-P_{G/e}(x).$ ➊

Proof. The valid colorings of $G-e$ can be divided into two groups: (1) those
where the ends of the edge $e$ get different colors — these remain to be valid
colorings of $G$ and (2) those where the ends of $e$ get the same color — each
of such colorings corresponds to a unique coloring of $G/e$. Hence

$P_{G-e}(x)=P_{G}(x)+P_{G/e}(x),$

which is equivalent to the deletion-minus-contraction formula ➊ ‣ 5. ∎

Note that if the pseudograph $G$ has loops, then $P_{G}(x)=0$ for any $x$.
Indeed, in a valid coloring the ends of a loop should get different colors,
which is impossible.

The latter can also be proved using the deletion-minus-contraction formula.
Indeed, if $e$ is a loop in $G$, then $G/e=G-e$. Therefore
$P_{G-e}(x)=\nobreak P_{G/e}(x)$ and

$P_{G}(x)=P_{G-e}(x)-P_{G/e}(x)=0.$

Similarly, removing a parallel edge from a pseudograph $G$ does not change the
value $P_{G}(x)$ for any $x$. Indeed, if $e$ is an edge of $G$ which has a
parallel edge $f$, then in $G/e$ the edge $f$ becomes a loop. Therefore
$P_{G/e}(x)=0$ for any $x$ and by the deletion-minus-contraction formula we
get that

$P_{G}(x)=P_{G-e}(x).$

The same identity can be seen directly — any admissible coloring of $G-e$ is
also admissible in $G$ — since the ends of $f$ get different colors, so does
$e$.

Summarizing the discussion above: the problem of finding $P_{G}(x)$ for a
pseudograph $G$ can be reduced to the case when $G$ is a graph; that is, $G$
has no loops and no parallel edges. Indeed, if $G$ has a loop, then
$P_{G}(x)=0$ for all $x$. Further, removing one of the parallel edges from $G$
does not change $P_{G}(x)$.

Recall that polynomial $P$ of $x$ is an expression of the following type

$P(x)=a_{0}+a_{1}{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}x+\dots+a_{n}{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}x^{n},$

with constants $a_{0},\dots,a_{n}$, which are called _coefficients_ of the
polynomial. The coefficient $a_{0}$ is called _free term_ of the polynomial.
If $a_{n}\neq 0$, it is called the _leading coefficient_ of $P$; in this case
$n$ is the degree of $P$. If the leading coefficient is 1, then the polynomial
is called _monic_.

5.4. Theorem. Let $G$ be a pseudograph with $p$ vertexes. Then $P_{G}(x)$ is a
polynomial with integer coefficients and vanishing free term.

Moreover, if $G$ has a loop, then $P_{G}(x)\equiv 0$; otherwise $P_{G}(x)$ is
monic and has degree $p$.

Based on this result we can call $P_{G}(x)$ the _chromatic polynomial_ of the
graph $G$. The deletion-minus-contraction formula will play the central role
in the proof.

Proof. As usual, denote by $p$ and $q$ the number of vertexes and edges in
$G$. To prove the first part, we will use the induction on $q$.

As the base case, consider the null graph $N_{p}$; that is, the graph with $p$
vertexes and no edges. Since $N_{p}$ has no edges, any coloring of $N_{p}$ is
admissible. We have $x$ choices for each of $n$ vertexes therefore

$P_{N_{p}}(x)=x^{p}.$

In particular, the function $x\mapsto P_{N_{p}}(x)$ is given by a monic
polynomial of degree $p$ with integer coefficients and vanishing free term.

Assume that the first statement holds for all pseudographs with at most $q-1$
edges. Fix a pseudograph $G$ with $q$ edges. Applying the deletion-minus-
contraction formula for some edge $e$ in $G$, we get that

$P_{G}(x)=P_{G-e}(x)-P_{G/e}(x).$ ➋

Note that the pseudographs $G-e$ and $G/e$ have $q-1$ edges. By the induction
hypothesis, $P_{G-e}(x)$ and $P_{G/e}(x)$ are polynomials with integer
coefficients and vanishing free terms. Hence ➋ ‣ 5 implies the same for
$P_{G}(x)$.

If $G$ has a loop, then $P_{G}(x)=0$, as $G$ has no valid colorings. It
remains to show that if $G$ has no loops, then $P_{G}(x)$ is a monic
polynomial of degree $p$.

Assume that the statement holds for any multigraph $G$ with at most $q-1$
edges and at most $p$ vertexes.

Fix a multigraph $G$ with $p$ vertexes and $q$ edges. Note that $G-e$ is a
multigraph with $p$ vertexes and $q-1$ edges. By the assumption, its chromatic
polynomial $P_{G-e}$ is monic of degree $p$.

Further the pseudograph $G/e$ has $p-1$ vertexes, and its chromatic polynomial
$P_{G/e}$ either vanishes or it has degree $p-1$. In both cases the difference
$P_{G-e}-P_{G/e}$ is a monic polynomial of degree $p$. It remains to apply ➋ ‣
5. ∎

5.5. Advanced exercise. Let $G$ be a graph with $p$ vertexes, $q$ edges, and
$n$ connected components. Show that

$P_{G}(x)=x^{p}-a_{p-1}{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}x^{p-1}+a_{p-2}{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}x^{p-2}+\dots+(-1)^{p-n}a_{n}{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}x^{n},$

where $a_{n},\dots,a_{p-1}$ are positive integers and $a_{p-1}=q$.

Hint: Apply induction on $q$ and use the deletion-minus-contraction formula
the same way as in the proof of the theorem.

5.6. Exercise. Use induction and the deletion-minus-contraction formula to
show that

  1. (a)

$P_{T}(x)=x{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}(x-1)^{q}$ for any tree $T$
with $q$ edges;

  2. (b)

$P_{C_{p}}(x)=(x-1)^{p}+(-1)^{p}{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}(x-1)$
for the cycle $C_{p}$ of length $p$.

  3. (c)

if $G$ is a graph with $p$ vertexes, then $P_{G}(x)\geqslant 0$ for any
$x\geqslant p-1$.

  4. (d)

$P_{F_{n}}(x)=x{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}(x-1){\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}(x-2)^{n-1}$, where $F_{n}$ denotes the
$n$-spine fan, defined on page 3.

  5. (e)

$P_{L_{n}}(x)=x{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}(x-1){\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}(x^{2}-3{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}x+3)^{n-1}$, where $L_{n}$ denotes the $n$-step ladder, defined on page
3.

5.7. Exercise. Show that graph $G$ is a tree if and only if

$P_{G}(x)=x{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}(x-1)^{p-1}$

for some positive integer $p$.

5.8. Exercise. Show that

$P_{K_{p}}(x)=x{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}(x-1)\cdots(x-p+1).$

Remark. Note that for any graph $G$ with $p$ vertexes we have

$P_{K_{p}}(x)\leqslant P_{G}(x)\leqslant P_{N_{p}}(x)$

for any $x$. Since both polynomials

$\displaystyle P_{K_{p}}(x)$ $\displaystyle=x{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}(x-1)\cdots(x-p+1),$ and $\displaystyle P_{N_{p}}(x)$
$\displaystyle=x^{p},$

are monic of degree $p$, it follows that so is $P_{G}$.

Hence Exercise 5 leads to an alternative way to prove the second statement in
Theorem 5.

5.9. Exercise. Construct a pair of nonisomorphic graphs with equal chromatic
polynomials.

### Matching polynomial

Recall that a _matching_ in a graph is a set of edges without common vertexes.

Given an integer $n\geqslant 0$, denote by $m_{n}=m_{n}(G)$ the number of
matchings with $n$ edges in the graph $G$.

Note that for a graph $G$ with $p$ vertexes and $q$ edges, we have
$m_{0}(G)=1$, $m_{1}(G)=q$, and if $2{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}n>p$, then $m_{n}(G)=0$. The maximal integer $k$ such that $m_{k}(G)\neq
0$ is called the _matching number_ of $G$. The expression

$M_{G}(x)=m_{0}+m_{1}{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}x+\dots+m_{k}{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}x^{k}$

is called the _matching polynomial_ of $G$.

The matching polynomial $M_{G}(x)$ conviniently organizes the numbers
$m_{n}(G)$ so we can work with all of them simultaneously. For example, the
degree of $M_{G}(x)$ is the matching number of $G$ and the total number of
matching in $G$ is its value at $1$:

$M_{G}(1)=m_{0}+m_{1}+\dots+m_{k}.$

5.10. Exercise. Assume that a graph $G$ has exactly two connected components
$H_{1}$ and $H_{2}$. Show that

$M_{G}(x)=M_{H_{1}}(x){\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}M_{H_{2}}(x)$

for any $x$.

5.11. Exercise. Show that the values

$\tfrac{1}{2}{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}[M_{G}(1)+M_{G}(-1)]\quad\text{and}\quad\tfrac{1}{2}{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}[M_{G}(1)-M_{G}(-1)]$

equal to the number of matchings with even and odd number of edges
correspondingly.

Assume $e$ is an edge in a graph $G$. Recall that the graph $G-e$ is obtained
by deleting $e$ from $G$. Let us denote by $G-[e]$ the graph obtained by
deleting the vertexes of $e$ with all their edges from $G$; that is, if $e$
connects two vertexes $v$ and $w$, then

$G-[e]=G-\\{v,w\\}.$

The following exercise is analogous to the deletion-contraction formulas 5 and
3.

5.12. Exercise. Let $G$ be a graph.

  1. (a)

Show that

$M_{G}(x)=M_{G-e}(x)+x{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}M_{G-[e]}(x)$

for any edge $e$ in $G$.

  2. (b)

Use part a to show that the matching polynomials of complete graphs satisfy
the following recursive relation:

$M_{K_{n+1}}(x)=M_{K_{n}}(x)+n{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}x{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}M_{K_{n-1}}(x).$

  3. (c)

Use b to calculate $M_{K_{n}}(x)$ for $1\leqslant n\leqslant 6$.

### Spanning-tree polynomial

Consider a connected graph $G$ with $p$ vertexes; assume $p\geqslant 2$.

Let us prepare independent variables $x_{1},\dots,x_{p}$, one for each vertex
of $G$. For each spanning tree $T$ in $G$ consider the monomial

$x_{1}^{d_{1}-1}\cdots x_{p}^{d_{p}-1},$

where $d_{i}$ denotes the degree of the $i$-th vertex in $T$.

The tree $T$ has $p-1$ edges and therefore $d_{1}+\dots+d_{p}=2{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}(p-1)$. It follows that the total degree of the
monomial is $p-2$.

The sum of these monomials is a polynomial of degree $p-2$ of $p$ variables
$x_{1},\dots,x_{p}$. This polynomial will be called the _spanning-tree
polynomial_ of $G$ and it will be denoted by $S_{G}(x_{1},\dots,x_{p})$.

For example, the graph $G$ shown on the diagram has three spanning trees; each
is obtained by deleting one of the edges in the cycle $xyz$. Abusing notation
slightly, let us use the same label for a vertex in $G$ and for the
corresponding variable. The monomial for the tree obtained by deleting the
edge $xy$ is $x^{2}{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}y{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}z$. Indeed, in this tree the vertex $x$ has
degree 3, vertexes $y$ and $z$ have degree $2$ and the remaining vertexes $u$,
$v$, and $w$ have degree 1. The monomials for the other two trees are
$x^{2}{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}z^{2}$ and $x^{3}{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}z$. Therefore

$S_{G}(x,y,z,u,v,w)=x^{2}{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}y{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}z+x^{2}{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}z^{2}+x^{3}{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}z.$

Note that $S_{G}(x,y,z,u,v,w)$ does not depend on $u$, $v$ and $w$ since the
corresponding vertexes have degree 1 in any spanning tree of $G$.

Note that $s(G)=S_{G}(1,\dots,1)$ for any graph $G$; that is,
$S_{G}(1,\dots,1)$ is the total number of spanning trees in $G$. Indeed each
spanning tree in $G$ contributes one monomial to $S_{G}$ and each monomial
contributes $1$ to the value $S_{G}(1,\dots,1)$. The following exercise shows
that, the polynomial $S_{G}$ keeps a lot more information about spanning trees
in $G$.

5.13. Exercise. Let $S_{G}(x_{1},\dots,x_{p})$ be the spanning-tree polynomial
of a graph $G$. Show the following:

  1. (a)

$S_{G}(0,1,\dots,1)$ is the number of spanning trees with a leaf at the first
vertex.

  2. (b)

The coefficient of $S_{G}$ in front of $x_{1}\cdots x_{p-2}$ equals to the
number of paths of length $p-1$ connecting $(p-1)$-th and $p$-th vertexes.

  3. (c)

The partial derivative

$\frac{\partial S_{G}}{\partial x_{1}}(0,1,\dots,1)$

is the numbers of spanning trees in $G$ with degree 2 at the first vertex.

  4. (d)

The two values

$\tfrac{1}{2}{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}\left[S_{G}(1,1,\dots,1)\pm S_{G}(-1,1,\dots,1)\right]$

are the numbers of spanning trees in $G$ with odd or correspondingly even
degree at the first vertex.

5.14. Theorem.

$S_{K_{p}}(x_{1},\dots,x_{p})=(x_{1}+\dots+x_{p})^{p-2},$

where $K_{p}$ is the complete graph with $p\geqslant 2$ vertexes.

Note that the theorem above generalizes the Cayley formula (4). Indeed,

$s(K_{p})=S_{K_{p}}(1,\dots,1)=(1+\dots+1)^{p-2}=p^{p-2}.$

In the proof we will use the following algebraic lemma; its proof is left to
the reader.

5.15. Lemma. Assume a polynomial $P(x_{1},\dots,x_{n})$ vanish if $x_{n}=0$,
then $P$ is divisible by $x_{n}$; that is, there is a polynomial
$Q(x_{1},\dots,x_{n})$ such that

$P(x_{1},\dots,x_{n})=x_{n}{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}Q(x_{1},\dots,x_{n}).$

Proof of 5. Let us apply induction on $p$; the base case $p=2$ is evident.

Assume that the statement holds for $p-1$; that is,

$S_{K_{p-1}}(x_{1},\dots,x_{p-1})-(x_{1}+\dots+x_{p-1})^{p-3}=0.$ ➌

We need to show that

$S_{K_{p}}(x_{1},\dots,x_{p-1},x_{p})-(x_{1}+\dots+x_{p-1}+x_{p})^{p-2}=0.$ ➍

First let us show that the equality holds if $x_{p}=0$; that is,

$S_{K_{p}}(x_{1},\dots,x_{p-1},0)-(x_{1}+\dots+x_{p-1})^{p-2}=0.$ ➎

Indeed, $S_{K_{p}}(x_{1},\dots,x_{p-1},0)$ is the sum of all monomials in
$S_{K_{p}}$ without $x_{p}$. Each of these monomials correspond to a spanning
tree $T$ in $K_{p}$ with $d_{p}=1$; in other words, $T$ has a leaf at
$x_{p}$.111We use $x_{i}$ as a label of a vertex in $K_{p}$ and as the
corresponding variable. Note that the tree $T$ is obtained from another tree
$T^{\prime}$ with the vertexes $x_{1},\dots,x_{p-1}$ by adding an edge from
$x_{p}$ to $x_{i}$ for some $i<p$.

Note that the monomial in $S_{K_{p}}$ that corresponds to $T$ equals to the
product of $x_{i}$ times the monomial in $S_{K_{p-1}}$ that corresponds to
$T^{\prime}$. To get the sum of all monomials in $S_{K_{p}}$ without $x_{p}$,
we need to sum up these products for all $i<p$ and all the monomials in
$S_{K_{p-1}}$; this way we get

$S_{K_{p-1}}(x_{1},\dots,x_{p-1}){\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}(x_{1}+\dots+x_{p-1}).$

By ➌ ‣ 5, the latter equals to

$(x_{1}+\dots+x_{p-1})^{p-2}$

which implies ➎ ‣ 5.

Now assume ➍ ‣ 5 does not hold. Denote by $P(x_{1},\dots,x_{p})$ the left hand
side in ➍ ‣ 5. Observe that $P$ is a _symmetric_ _homogeneous_ polynomial of
degree $p-\nobreak 2$. That is, any permutation of values $x_{1},\dots,x_{p}$
does not change $P(x_{1},\dots,x_{p})$ and each monomial in $P$ has total
degree $p-2$.

By Lemma 5 and ➎ ‣ 5, we get that $P$ is divisible by $x_{p}$. Since $P$ is
symmetric it is divisible by each $x_{i}$; that is, there is a polynomial
$Q(x_{1},\dots,x_{p})$ such that

$P(x_{1},\dots,x_{p})=x_{1}\cdots x_{p}{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}Q(x_{1},\dots,x_{p}).$

Since $P\neq 0$, the total degree of $P$ is at least $p$. But $P$ has degree
$p-2$, a contraction. ∎

5.16. Exercise. Show that the number of spanning trees in $K_{p}$ with degree
$k$ at the first vertex equals to $\tbinom{p-2}{k-1}{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}(p-1)^{p-k-1}$.

Hint: Calculate $N=\tfrac{\partial^{k-1}}{\partial
x_{1}^{k-1}}S_{K_{n}}(0,1,\dots,1)$ using the expression for $S_{K_{n}}$ given
in Theorem 5 and determine how much a tree with degree $d$ at the first vertex
contributes to the value $N$.

5.17. Exercise. Assume that the vertexes of the left part of $K_{m,n}$ have
corresponding variables $x_{1},\dots,x_{m}$ and the vertexes in the right part
have corresponding variables $y_{1},\dots,y_{n}$. Show that

$S_{K_{m,n}}(x_{1},\dots,x_{m},y_{1},\dots,y_{n})=(x_{1}+\dots+x_{m})^{n-1}{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}(y_{1}+\dots+y_{n})^{m-1}.$

Conclude that $s(K_{m,n})=m^{n-1}{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}n^{m-1}$.

Hint: Modify the proof of Theorem 5.

### Remarks

Very good expository papers on chromatic polynomials are written by Ronald
Read [31] and Alexandr Evnin [10]. Matching polynomials are discussed in a
paper of Christopher Godsil and Ivan Gutman [13].

Our discussion of spanning-tree polynomials is based on a modification of
Fedor Petrov [29] of the original proof of Arthur Cayley [4].

Generating functions discussed in Chapter 6 give connections between graph
theory and power series; this subject is more challenging, but worth to learn.

##  Chapter 6 Generating functions

For this chapter, the reader has to be familiar with power series.

### Exponential generating functions

The power series

$A(x)=a_{0}+a_{1}{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}x+\tfrac{1}{2}{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}a_{2}{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}x^{2}+\dots+\tfrac{1}{n!}{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}a_{n}{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}x^{n}+\dots$

is called the _exponential generating function_ of the sequence
$a_{0},a_{1},\dots$

If the series $A(x)$ converges in some neighborhood of zero, then it defines a
function which remembers all information of the sequence $a_{n}$. The latter
follows since

$A^{(n)}(0)=a_{n};$ ➊

that is, the $n$-th derivative of $A(x)$ at $0$ equals to $a_{n}$.

However, without assuming the convergence, we can treat $A(x)$ as a formal
power series. We are about to describe how to add, multiply, take the
derivative, and do other operations with formal power series.

Sum and product. Consider two exponential generating functions

$\displaystyle A(x)$ $\displaystyle=a_{0}+a_{1}{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}x+\tfrac{1}{2}{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}a_{2}{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}x^{2}+\tfrac{1}{6}{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}a_{3}{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}x^{3}+\dots$ $\displaystyle B(x)$ $\displaystyle=b_{0}+b_{1}{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}x+\tfrac{1}{2}{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}b_{2}{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}x^{2}+\tfrac{1}{6}{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}b_{3}{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}x^{3}+\dots$

We will write

$S(x)=A(x)+B(x),\quad P(x)=A(x){\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}B(x)$

if the power series $S(x)$ and $P(x)$ are obtained from $A(x)$ and $B(x)$ by
opening the parentheses of these formulas and combining like terms.

It is straightforward to check that $S(x)$ is the exponential generating
function for the sequence

$\displaystyle s_{0}$ $\displaystyle=a_{0}+b_{0},$ $\displaystyle s_{1}$
$\displaystyle=a_{1}+b_{1},$ $\displaystyle\dots$ $\displaystyle s_{n}$
$\displaystyle=a_{n}+b_{n}.$

The product $P(x)$ is also exponential generating function for the sequence

$\displaystyle p_{0}$ $\displaystyle=a_{0}{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}b_{0},$ ➋ $\displaystyle p_{1}$ $\displaystyle=a_{0}{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}b_{1}+a_{1}{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}b_{0},$ $\displaystyle p_{2}$ $\displaystyle=a_{0}{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}b_{2}+2{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}a_{1}{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}b_{1}+a_{2}{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}b_{0},$ $\displaystyle p_{3}$
$\displaystyle=a_{0}{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}b_{3}+3{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}a_{1}{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}b_{2}+3{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}a_{2}{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}b_{1}+a_{3}{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}b_{0},$ $\displaystyle\dots$ $\displaystyle p_{n}$
$\displaystyle=\sum_{i=0}^{n}\tbinom{n}{i}{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}a_{i}{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}b_{n-i}.$

6.1. Exercise. Assume $A(x)$ is the exponential generating function of the
sequence $a_{0},a_{1},\dots$. Show that $B(x)=x{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}A(x)$ corresponds to the sequence
$b_{n}=n{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}a_{n-1}$.

Composition. Once we define addition and multiplication of power series we can
also plug in one power series in another. For example, if $a_{0}=0$, then the
expression

$E(x)=e^{A(x)}$

is another power series which is obtained by plugging $A(x)$ instead of $x$ in
the power series of exponent:

$e^{x}=1+x+\tfrac{1}{2}{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}x^{2}+\tfrac{1}{6}{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}x^{3}+\dots$

It is harder to express the sequence $(e_{n})$ corresponding to $E(x)$ in
terms of $a_{n}$, but it is easy to find the first few terms. Since we assume
$a_{0}=0$, we have

$\displaystyle e_{0}$ $\displaystyle=1,$ $\displaystyle e_{1}$
$\displaystyle=a_{1},$ $\displaystyle e_{2}$ $\displaystyle=a_{2}+2{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}a_{1}^{2},$ $\displaystyle e_{3}$
$\displaystyle=a_{3}+6{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}a_{1}{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}a_{2},$ $\displaystyle\dots$

Derivative. The derivative of

$A(x)=a_{0}+a_{1}{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}x+\tfrac{1}{2}{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}a_{2}{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}x^{2}+\dots+\tfrac{1}{n!}{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}a_{n}{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}x^{n}+\dots$

is defined as the following formal power series

$A^{\prime}(x)=a_{1}+a_{2}{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}x+\tfrac{1}{2}{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}a_{3}{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}x^{2}+\dots+\tfrac{1}{n!}{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}a_{n+1}{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}x^{n}+\dots$

Note that $A^{\prime}(x)$ coincides with the ordinary derivative of $A(x)$ if
the latter converges.

Note that $A^{\prime}(x)$ is the exponential generating function of the
sequence

$a_{1},a_{2},a_{3},\dots$

obtained from the original sequence

$a_{0},a_{1},a_{2},\dots$

by deleting the zero-term and shifting the indexes by 1.

6.2. Exercise. Let $A(x)$ be the exponential generating function of the
sequence $a_{0},a_{1},a_{2}\dots$. Describe the sequence $b_{n}$ with the
exponential generating function

$B(x)=x{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}A^{\prime}(x).$

Calculus. If $A(x)$ converges and

$E(x)=e^{A(x)},$

then we have

$\ln E(x)=A(x).$

Also by taking the derivative of $E(x)=e^{A(x)}$ we get that

$\displaystyle E^{\prime}(x)$ $\displaystyle=e^{A(x)}{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}A^{\prime}(x)=$ $\displaystyle=E(x){\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}A^{\prime}(x).$

These identities have a perfect meaning in terms of formal power series and
they still hold without assuming the convergence. We will not prove it
formally, but this is not hard.

### Fibonacci numbers

Recall that Fibonacci numbers $f_{n}$ are defined using the recursive identity
$f_{n+1}=f_{n}+f_{n-1}$ with $f_{0}=0$, $f_{1}=1$.

6.3. Exercise. Let $F(x)$ be the exponential generating function of Fibonacci
numbers $f_{n}$.

  1. (a)

Show that it satisfies the following differential equation

$F^{\prime\prime}(x)=F(x)+F^{\prime}(x).$

  2. (b)

Conclude that

$F(x)=\frac{1}{\sqrt{5}}{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}\left(e^{\frac{1+\sqrt{5}}{2}{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}x}-e^{\frac{1-\sqrt{5}}{2}{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}x}\right).$

  3. (c)

Use the identity ➊ ‣ 6 to derive

$f_{n}=\tfrac{1}{\sqrt{5}}{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}\left((\tfrac{1+\sqrt{5}}{2})^{n}-(\tfrac{1+\sqrt{5}}{2})^{n}\right).$

(This is the so called _Binet’s formula_.)

### Exponential formula

Fix a set of graphs $\mathcal{S}$. Denote by $c_{n}=c_{n}(\mathcal{S})$ the
number of spanning subgraphs of $K_{n}$ isomorphic to one of the graphs in
$\mathcal{S}$. Let

$C(x)=C_{\mathcal{S}}(x)$

be the exponential generating function of the sequence $c_{n}$.

6.4. Theorem. Let $\mathcal{S}$ be a set of connected graphs.

  1. (a)

Fix a positive integer $k$ and denote by $w_{n}$ the number of spanning
subgraphs of $K_{n}$ which have exactly $k$ connected components, and each
connected component is isomorphic to one of the graphs in $\mathcal{S}$. Then

$W_{k}(x)=\tfrac{1}{k!}{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}C_{\mathcal{S}}(x)^{k},$

where $W_{k}(x)$ is the exponential generating function of the sequence
$w_{n}$.

  2. (b)

Denote by $a_{n}$ the number of _all_ spanning subgraphs of $K_{n}$ such that
each connected component of it is from the class $\mathcal{S}$. Let $A(x)$ be
the exponential generating function of the sequence $(a_{n})$. Then

$1+A(x)=e^{C_{\mathcal{S}}(x)}.$

Taking the logarithm and derivative of the formula in b, we get the following:

6.5. Corollary. Assume $A(x)$ and $C(x)$ as in Theorem 6b. Then

$\ln[1+A(x)]=C(x)\quad\text{and}\quad A^{\prime}(x)=[1+A(x)]{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}C^{\prime}(x).$

The second formula in this corollary provides a recursive formula for the
corresponding sequences which will be important later.

Proof; a. Denote by $v_{n}$ the number of spanning subgraphs of $K_{n}$ which
have $k$ ordered connected components and each connected component is
isomorphic to one of the graphs in $\mathcal{S}$. Let $V_{k}(x)$ be the
corresponding generating function.

Note that for each graph described above there are $k!$ ways to order its $k$
components. Therefore $w_{n}=\tfrac{1}{k!}{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}v_{n}$ for any $n$ and

$W_{k}(x)=\tfrac{1}{k!}{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}V_{k}(x).$

Hence it is sufficient to show that

$V_{k}(x)=C(x)^{k}.$ ➌

To prove the latter identity, we apply induction on $k$ and the multiplication
formula ➋ ‣ 6 for exponential generating functions. The base case $k=1$ is
evident.

Assuming that the identity ➌ ‣ 6 holds for $k$; we need to show that

$V_{k+1}=V_{k}(x){\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}C(x).$ ➍

Assume that a spanning graph with $k+1$ ordered connected components of
$K_{n}$ is given. Denote by $m$ the number of vertexes in the first $k$
components. There are $\tbinom{n}{m}$ ways to choose these $m$ vertexes among
$n$ vertexes of $K_{n}$. For each choice, we have $v_{m}$ ways to choose a
spanning subgraph with $k$ components in it. The last component has $m-n$
vertexes and we have $c_{n-m}$ ways to choose a subgraph from $\mathcal{S}$.
All together, we get

$\tbinom{n}{m}{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}v_{m}{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}c_{n}$

spanning graphs with $k+1$ ordered connected components and $m$ vertexes in
the first $k$ components. Summing it up for all $m$, we get the multiplication
formula ➋ ‣ 6 for exponential generating functions; hence ➍ ‣ 6 follows.

b. Note that $a_{n}$ is the sum of numbers of spanning graphs in $K_{n}$ with
$1,2,\dots$ components. That is,

$\displaystyle A(x)$ $\displaystyle=W_{1}(x)+W_{2}(x)+\dots=$ applying part a,
we can continue $\displaystyle=C(x)+\tfrac{1}{2}{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}C(x)^{2}+\tfrac{1}{6}{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}C(x)^{3}+\dots=$ since
$e^{x}=1+x+\tfrac{1}{2}{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}x^{2}+\tfrac{1}{6}{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}x^{3}+\dots$,
we can rewrite it as $\displaystyle=e^{C(x)}-1.$

∎

### Perfect matchings

Recall that a _perfect matching_ is a 1-factor of the graph. In other words,
it is a set of isolated edges which covers all the vertexes. Note that if a
graph admits a perfect matching, then the number of its vertexes is even.

The _double factorial_ is defined as the product of all the integers from $1$
up to some non-negative integer $n$ that have the same parity (odd or even) as
$n$; the double factorial of $n$ is denoted by $n!!$. For example,

$9!!=9{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}7{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}5{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}3{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}1=945\quad\text{and}\quad 10!!=10{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}8{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}6{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}4{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}2=3840.$

6.6. Exercise. Let $a_{n}$ denote the number of perfect matchings in $K_{n}$.
Show that

  1. (a)

$a_{2}=1$;

  2. (b)

$a_{n}=0$ for any odd $n$;

  3. (c)

$a_{n+1}=n{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}a_{n-1}$ for any integer
$n\geqslant 2$.

  4. (d)

Conclude that $a_{n}=0$ and $a_{n+1}=n!!$ for any oodd $n$.

Now we give a more complicated proof of Exercise 6d.

6.7. Problem. Use Theorem 6 to show that the number of perfect matching in
$K_{2{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}n}$ is $(2{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}n-1)!!$.

Solution. Denote by $a_{n}$ the number of perfect matchings in $K_{n}$ and let
$A(x)$ be the corresponding exponential generating function.

Note that a perfect matching can be defined as a spanning subgraph such that
each connected component is isomorphic to $K_{2}$. So we can apply the formula
in Theorem 6 for the set $\mathcal{S}$ consisting of only one graph $K_{2}$.

Note that if $K_{n}$ contains a spanning subgraph isomorphic to $K_{2}$, then
$n=2$. It follows that $c_{2}(\mathcal{S})=1$ and $c_{n}(\mathcal{S})=0$ for
$n\neq 2$. Therefore

$C(x)=C_{\mathcal{S}}(x)=\tfrac{1}{2}{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}x^{2}.$

By Theorem 6b,

$\displaystyle 1+A(x)$ $\displaystyle=e^{C(x)}=$
$\displaystyle=e^{\frac{1}{2}{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}x^{2}}=$
$\displaystyle=1+\tfrac{1}{2}{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}x^{2}+\tfrac{1}{2{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}4}{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}x^{4}+\tfrac{1}{6{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}8}{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}x^{6}+\dots+\tfrac{1}{n!{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}2^{n}}{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}x^{2{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}n}+\dots$

That is,

$\tfrac{1}{(2{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}n-1)!}{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}a_{2{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}n-1}=0\quad\text{and}\quad\tfrac{1}{(2{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}n)!}{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}a_{2{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}n}=\tfrac{1}{n!{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}2^{n}}$

for any positive integer $n$. In particular,

$\displaystyle a_{2{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}n}$
$\displaystyle=\frac{(2{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}n)!}{n!{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}2^{n}}=$ $\displaystyle=\frac{1{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}2\cdots(2{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}n)}{2{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}4\cdots(2{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}n)}=$ $\displaystyle=1{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}3\cdots(2{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}n-1)=$ $\displaystyle=(2{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}n-1)!!$

That is, $a_{n}=0$ for any odd $n$ and $a_{n}=(n-1)!!$ for even $n$. ∎

Remark. Note that by Corollary 6, we also have

$A^{\prime}(x)=[1+A(x)]{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}x,$

which is equivalent to the recursive identity

$a_{n+1}=n{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}a_{n-1}$

in Exercise 6c.

### All matchings

Now let $\mathcal{S}$ be the set of two graphs $K_{1}$ and $K_{2}$. Evidently
$c_{1}(\mathcal{S})=\nobreak c_{2}(\mathcal{S})=1$. Further, we have that
$c_{n}(\mathcal{S})=0$ for all $n\geqslant 3$ since $K_{n}$ contains no
spanning subgraphs isomorphic to $K_{1}$ or $K_{2}$.

Therefore the exponential generating function of the sequence
$c_{n}(\mathcal{S})$ is a polynomial of degree 2

$C(x)=x+\tfrac{1}{2}{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}x^{2}.$

Note that a matching in a graph $G$ can be identified with a spanning subgraph
with all connected components isomorphic to $K_{1}$ or $K_{2}$. If we denote
by $a_{n}$ the number of all matchings and by $A(x)$ the corresponding
exponential generating function, then by Theorem 6b, we get that

$A(x)=e^{x+\frac{1}{2}{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}x^{2}}-1.$

Applying Corollary 6, we also have

$A^{\prime}(x)=[1+A(x)]{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}(1+x).$

The latter is equivalent to the following recursive formula for $a_{n}$:

$a_{n+1}=a_{n}+n{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}a_{n-1}.$ ➎

Since $a_{1}=1$ and $a_{2}=2$, we can easily find first the few terms of this
sequence:

$1,2,4,10,26,\dots$

6.8. Exercise. Prove formula ➎ ‣ 6 directly — without using generating
functions. Compare to Exercise 5b.

### Two-factors

Let $\mathcal{S}$ be the set of all cycles.

Note that a _$2$ -factor_ of a graph can be defined as a spanning subgraph
with components isomorphic to cycles. Denote by $a_{n}$ and $c_{n}$ the number
of $2$-factors and _spanning cycles_ 111Also known as _Hamiltonian cycles_. in
$K_{n}$ respectively. Let $A(x)$ and $C(x)$ be the corresponding exponential
generating functions.

6.9. Exercise.

  1. (a)

Show that $c_{1}=c_{2}=0$ and

$c_{n}=(n-1)!/2$

for $n\geqslant 3$. In particular,

$c_{1}=0,c_{2}=0,c_{3}=1,c_{4}=3,c_{5}=12,c_{6}=60.$

  2. (b)

Use part a and the identity

$A^{\prime}(x)=[1+A(x)]{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}C^{\prime}(x)$

to find $a_{1},\dots,a_{6}$.

  3. (c)

Count the number of 2-factors in $K_{1},\dots,K_{6}$ by hand, and compare it
to the result in part b.

  4. (d)

Use part a to conclude that

$C(x)=-\tfrac{1}{2}{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}\ln(1-x)-\tfrac{1}{2}{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}x-\tfrac{1}{4}{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}x^{2}.$

  5. (e)

Use part d and Theorem 6b to show that

$A(x)=\frac{1}{e^{\frac{x}{2}+\frac{x^{2}}{4}}{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}\sqrt{1-x}}-1.$

### Counting spanning forests

Recall that a _forest_ is a graph without cycles. Assume we want to count the
number of spanning forests in $K_{n}$; denote by $a_{n}$ its number and by
$c_{n}$ the number of connected spanning forests. That is, $c_{n}$ is the
number of spanning trees in $K_{n}$. For example, $K_{3}$ has the following 7
spanning forests; therefore $a_{3}=\nobreak 7$.

By Corollary 6, the following identity

$A^{\prime}(x)=[1+A(x)]{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}C^{\prime}(x)$

holds for the corresponding exponential generating functions.

According to the Cayley theorem, $c_{n}=n^{n-2}$; in particular,

$c_{1}=1,c_{2}=1,c_{3}=3,c_{4}=16,\dots$

Applying the product formula ➋ ‣ 6, we can use $c_{n}$ to calculate $a_{n}$
recurrently:

$\displaystyle a_{1}$ $\displaystyle=c_{1}=1,$ $\displaystyle a_{2}$
$\displaystyle=c_{2}+a_{1}{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}c_{1}=$
$\displaystyle=1+1{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}1=2,$ $\displaystyle
a_{3}$ $\displaystyle=c_{3}+2{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}a_{1}{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}c_{2}+a_{2}{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}c_{1}=$ $\displaystyle=3+2{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}1{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}1+2{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}1=7,$ $\displaystyle a_{4}$
$\displaystyle=c_{4}+3{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}a_{1}{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}c_{3}+3{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}a_{2}{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}c_{2}+a_{3}{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}c_{1}=$ $\displaystyle=16+3{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}1{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}3+3{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}2{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}1+7{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}1=38$
$\displaystyle\dots$

It is instructive to check by hand that there are exactly $38$ spanning
forests in $K_{4}$.

For the general term of $a_{n}$, no simple formula is known, however the
recursive formula above provides a sufficiently fast way to calculate its
terms.

### Counting connected subgraphs

Let $a_{n}$ be the number of all spanning subgraphs of $K_{n}$ and $c_{n}$ be
the number of connected spanning subgraphs of $K_{n}$. All 4 connected
spanning subgraphs of $K_{3}$ are shown on the diagram; therefore $c_{3}=4$.

Assume $A(x)$ and $C(x)$ are the corresponding exponential generating
functions. These two series diverge for all $x\neq 0$; nevertheless, the
formula for formal power series in Theorem 6b still holds, and by Corollary 6
we can write

$A^{\prime}(x)=[1+A(x)]{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}C^{\prime}(x).$

Note that $a_{n}=2^{\binom{n}{2}}$; indeed, to describe a subgraph of $K_{n}$
we can choose any subset of $\tbinom{n}{2}$ edges of $K_{n}$, and $a_{n}$ is
the total number of $\binom{n}{2}$ these independent choices. In particular,
the first few terms of $a_{n}$ are

$a_{1}=1,\quad a_{2}=2,\quad a_{3}=8,\quad a_{4}=64,\quad\dots$

Applying the product formula ➋ ‣ 6, we can calculate the first few terms of
$c_{n}$:

$\displaystyle c_{1}$ $\displaystyle=a_{1}=1$ $\displaystyle c_{2}$
$\displaystyle=a_{2}-a_{1}{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}c_{1}=$
$\displaystyle=2-1{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}1=1,$ $\displaystyle
c_{3}$ $\displaystyle=a_{3}-2{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}a_{1}{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}c_{2}-a_{2}{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}c_{1}=$ $\displaystyle=8-2{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}1{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}1-2{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}1=4,$ $\displaystyle c_{4}$
$\displaystyle=a_{4}-3{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}a_{1}{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}c_{3}-3{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}a_{2}{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}c_{2}-1{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}a_{3}{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}c_{1}=$ $\displaystyle=64-3{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}1{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}4-3{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}2{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}1-1{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}8{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}1=38,$ $\displaystyle\dots$

Note that in the previous section we found $a_{n}$ from $c_{n}$, and now we go
in the opposite direction. No closed formula is known for $c_{n}$, but the
recursive formula gives a sufficiently good way to calculate it.

### Remarks

The method of generating functions was introduced and widely used by Leonard
Euler; the term _generating function_ was coined later by Pierre Laplace. For
more on the subject, we recommend a classic book of Frank Harary and Edgar
Palmer [17].

Let us mention another application of exponential generating functions.

Assume $r_{n}$ denotes the number of rooted spanning trees in $K_{n}$. (A tree
with one marked vertex is called a _rooted tree_ and the marked vertex is
called its _root_). Then it is not hard to see that the exponential generating
function of $r_{n}$ satisfies the following identity

$R(x)=x{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}e^{R(x)}.$ ➏

By the Lagrange inversion theorem, formula ➏ ‣ 6 implies that $r_{n}=n^{n-1}$.

Since in any spanning tree of $K_{n}$ we have $n$ choices for the root, we
have that

$r_{n}=n{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}s(K_{n}).$

This way we get another proof of the Cayley formula (4)

$s(K_{n})=n^{n-2}.$

##  Chapter 7 Minimum spanning trees

### Optimization problems

We say that a graph $G$ has _weighted edges_ if each edge in $G$ is labeled by
a real number, called its _weight_. In this case the _weight of a subgraph_
$H$ (briefly $\mathop{\rm weight}\nolimits(H)$) is defined as the sum of the
weights of its edges.

An _optimization problem_ typically asks to minimize weight of a subgraph of a
certain type. A classic example is the so called _traveling salesman problem_.
It asks to find a Hamiltonian cycle with minimal weight (if it exists in the
graph).

No fast algorithm is known to solve this problem and it is expected that no
fast algorithm exists. We say _fast_ if the required time depends polynomially
on the number of the vertexes in the graph. The best known algorithms require
exponential time, which is just a bit better than a brute force checking of
all possible Hamiltonian cycles.

In fact the traveling salesman problem is a classic example of the so called
_NP-hard problems_ ; it means that if you find a fast algorithm to solve it,
then you solve the _P=NP problem_ — the most important question in modern
mathematics.

The so called _nearest neighbor algorithm_ gives a heuristic way to find a
Hamiltonian cycle with small (but not necessary smallest) weight. In the
following description, we assume that the graph is complete.

  1. (i)

Start at an arbitrary vertex.

  2. (ii)

Find the edge with minimal weight connecting the current vertex $v$ and an
unvisited vertex $w$ and move to $w$.

  3. (iii)

Repeat step ii until all vertexes are visited and then return to the original
vertex. This way we walked along a Hamiltonian cycle.

The nearest neighbor algorithm is an example of _greedy algorithms_ ; in other
words, it chooses the cheapest step at each stage. The cheap choices at the
beginning might force it to make expansive choices at the end, so it may not
find an optimal solution. In fact a greedy algorithm might give the worse
solution. For example, if we start from the vertex $a$ in the shown weighted
graph, then nearest neighbor algorithm produce the cycle $abcd$ which is the
worse — this cycle has total weight $11=1+1+5+4$ and the other two Hamiltonian
cycles have weights $9$ and $10$.

Let us list a few other classic examples of optimization problems. Unlike the
traveling salesman problem, there are fast algorithms which solve them.

  * $\diamond$

The _shortest path problem_ asks for a path with minimal weight, connecting
two given vertexes. It can be thought as optimal driving directions between
two locations.

  * $\diamond$

The _assignment problem_ asks for a matching of a given size with minimal
weight, in a bipartite graph. It can be used to minimize the total cost of
work, assuming that available workers charge different prices for each task.
This problem is closely related to the subject of the next chapter.

  * $\diamond$

The _minimum spanning tree problem_ asks for a spanning tree with minimal
weight. For example, we may think of minimizing the cost to build a computer
network between given locations. This problem will be the main subject of the
remaining sections of this chapter.

### Neighbors of a spanning tree

Let $G$ be a connected graph. Suppose $T$ and $T^{\prime}$ are spanning trees
in $G$. If

$T^{\prime}=T-e+e^{\prime}$

for some edges $e$ and $e^{\prime}$, then we say that $T^{\prime}$ is a
_neighbor_ of $T$.

7.1. Exercise. Let $G$ be a connected graph that is not a tree. Suppose that
any two distinct spanning trees in $G$ are neighbors. Show that $G$ has
exactly one cycle.

7.2. Theorem. Let $G$ be a graph with weighted edges. A spanning tree $T$ in
$G$ has minimal weight if and only if

$\mathop{\rm weight}\nolimits(T)\leqslant\mathop{\rm
weight}\nolimits(T^{\prime})$

for any neighbor $T^{\prime}$ of $T$.

7.3. Exchange lemma. Let $S$ and $T$ be spanning trees in a graph $G$. Then
for any edge $s$ in $S$ that is not in $T$ there is an edge $t$ in $T$, but
not in $S$ such that the subgraphs

$S^{\prime}=S-s+t\quad\text{and}\quad T^{\prime}=T+s-t$

are spanning trees in $G$.

Proof. Note that $S-s$ has two components, denote them by $S_{1}$ and $S_{2}$.

Let $P$ be a path in $T$ that connects the vertexes of $s$. Note that the path
$P$ starts in $S_{1}$ and ends in $S_{2}$. Therefore one of the edges of $P$,
say $t$, connects $S_{1}$ to $S_{2}$.

The subgraph $T+s$ has a cycle created by $P$ and $s$. Removing the edge $t$
from this cycle leaves a connected subgraph $T^{\prime}=T-t+s$. Evidently
$T^{\prime}$ and $T$ have the same number of vertexes and edges; since $T$ is
a tree, so is $T^{\prime}$.

Further $S^{\prime}=S-s+t=S_{1}+S_{2}+t$. Since $t$ connects two connected
subgraphs $S_{1}$ and $S_{2}$, the resulting subgraph $S^{\prime}$ is
connected. Again $S^{\prime}$ and $S$ have the same number of vertexes and
edges; since $S$ is a tree, so is $S^{\prime}$. ∎

Proof of 7. The ‘‘only-if’’ part is trivial — if $T$ has minimal weight among
all spanning trees, then, in particular, it has to be minimal among its
neighbors. It remains to show the ‘‘if’’ part.

Suppose that a spanning tree $T$ has the minimal weight among its neighbors.
Consider a minimum weight spanning tree $S$ in $G$; if there are more than
one, then we assume in addition that $S$ shares with $T$ the maximal number of
edges.

Arguing by contradiction, assume $T$ is not a minimum weight spanning tree; in
this case $T\neq S$. Then there is an edge $s$ in $S$, but not in $T$. Let $t$
be an edge in $T$ provided by the exchange lemma; in particular,
$S^{\prime}=S-s+t$ and $T^{\prime}=T+s-t$ are spanning trees.

Since $T^{\prime}$ is a neighbor of $T$, we have

$\displaystyle\mathop{\rm weight}\nolimits(T)$
$\displaystyle\leqslant\mathop{\rm weight}\nolimits(T^{\prime})=$
$\displaystyle=\mathop{\rm weight}\nolimits(T)+\mathop{\rm
weight}\nolimits(s)-\mathop{\rm weight}\nolimits(t).$ Therefore $\mathop{\rm
weight}\nolimits(s)\geqslant\mathop{\rm weight}\nolimits(t)$ and
$\displaystyle\mathop{\rm weight}\nolimits(S^{\prime})$
$\displaystyle=\mathop{\rm weight}\nolimits(S)-\mathop{\rm
weight}\nolimits(s)+\mathop{\rm weight}\nolimits(t)\leqslant$
$\displaystyle\leqslant\mathop{\rm weight}\nolimits(S).$

Since $S$ has minimal weight, we have an equality in the last inequality. That
is, $S^{\prime}$ is another minimum weight spanning tree in $G$. By
construction, $S^{\prime}$ has one more common edge with $T$; the latter
contradicts the choice of $S$. ∎

7.4. Exercise. Let $G$ be a graph with weighted edges and $T$ a minimal weight
spanning tree in $G$.

Suppose that for each edge $e$, we change its weight from $w$ to $2^{w}$. Show
that $T$ remains a minimal weight spanning tree in $G$ with the new weights.

### Kruskal’s algorithm

Kruskal’s algorithm finds a minimum weight spanning tree in a given connected
graph. If the graph is not connected, the algorithm finds a spanning tree in
each component of the graph. Let us describe it informally.

  1. (i)

Suppose $G$ is a graph with weighted edges. Start with the spanning forest $F$
in $G$ formed by all vertexes and no edges.

  2. (ii)

Remove from $G$ an edge with minimal weight. If this edge connects different
trees in $F$, then add it to $F$.

  3. (iii)

Repeat the procedure while $G$ has any remaining edges.

Note that Kruskal’s algorithm is _greedy_ — it chooses the cheapest step at
each stage.

7.5. Theorem. Kruskal’s algorithm finds a minimum weight spanning tree in any
connected pseudograph with weighted edges.

Proof. Evidently the the subgraph $F$ remains to be a forest at all stages. If
at the end, $F$ has more than one component, then the original graph $G$ could
not have edges connecting these components; otherwise the algorithm would
choose it at some stage. Therefore the resulting graph is a tree.

Suppose the spanning tree $T$ produced by Kruskal’s algorithm does not have
minimal total weight. Then $T$ does not satisfy Theorem 7; that is, there is a
neighbor $T^{\prime}=T+e^{\prime}-e$ of $T$ such that

$\displaystyle\mathop{\rm weight}\nolimits(T)$ $\displaystyle>\mathop{\rm
weight}\nolimits(T^{\prime})=$ $\displaystyle=\mathop{\rm
weight}\nolimits(T)+\mathop{\rm weight}\nolimits(e^{\prime})-\mathop{\rm
weight}\nolimits(e).$

Therefore $\mathop{\rm weight}\nolimits(e^{\prime})<\mathop{\rm
weight}\nolimits(e)$.

Denote by $F$ the forest at the stage right before adding $e$ to it. Note that
$F$ is a subgraph of $T-e$. Since $e^{\prime}$ connects different trees in
$T-e$, it connects different trees in $F$. But $\mathop{\rm
weight}\nolimits(e)>\mathop{\rm weight}\nolimits(e^{\prime})$, therefore the
algorithm should reject $e$ at this stage — a contradiction. ∎

### Other algorithms

Let us describe two more algorithms which find a minimal weight spanning tree
in a given connected graph $G$. For simplicity, we assume that $G$ has
distinct weights.

Prim’s algorithm.

  1. (i)

Start with a tree $T$ formed by a single vertex $v$ in $G$.

  2. (ii)

Choose an edge $e$ with the minimal weight that connects $T$ to a vertex not
yet in the tree. Add $e$ to $T$.

  3. (iii)

Repeat step ii until all vertexes are in the tree $T$.

Borůvka’s algorithm.

  1. (i)

Start with the forest $F$ formed by all vertexes of $G$ and no edges.

  2. (ii)

For each component $T$ of $F$, find an edge $e$ with minimal weight that
connects $T$ to another component of $F$; add $e$ to $F$.

  3. (iii)

Repeat step ii until $F$ has one component.

7.6. Exercise. Show that (a) Prim’s algorithm and (b) Borůvka’s algorithm
produce a minimum weight spanning tree of a given connected graph with all
different weights.

Hint: Mimic the proof for Kruskal’s algorithm.

7.7. Exercise. Compare Kruskal’s algorithm, Prim’s algorithm, and Borůvka’s
algorithm. Which one should work faster? When and why?

7.8. Exercise. Assume $G$ is a connected graph with weighted edges and all
weights are different. Let $T$ be a minimum weight spanning tree in $G$.

  1. (a)

Suppose $v$ is an end vertex in $G$ and $e$ is its adjacent edge. Show that
$e$ belongs to $T$.

  2. (b)

Suppose $C$ is a cycle in $T$ and $f$ is an edge in $C$ with maximal weight.
Show that $f$ does not belong to $T$.

  3. (c)

Find a minimum-spanning-tree algorithm that is based on observations a and b.

### Remarks

The NP-hardness of the traveling salesman problem follows from a result of
Richard Karp [23]. The discussed algorithms are named after Joseph Kruskal,
Robert Prim and Otakar Borůvka. Joseph Kruskal also described the so called
_reverse-delete algorithm_ [26] which is closely relevant to a solution of
Exercise 7. Prim’s algorithm was first discovered by Vojtěch Jarník,
rediscovered independently two times: by Robert Prim and by Edsger Dijkstra.

For more on optimization problems read a book by Dieter Jungnickel [21]. A
reader friendly introduction to P=NP problem is given in a book by Thomas
Cormen, Charles Leiserson, Ronald Rivest, and Slifford Stein [5, Chapter 34].

##  Chapter 8 Marriage theorem
and its relatives

### Alternating and augmenting paths

Recall that a _matching_ in a graph is a set of edges without common vertexes.

Let $M$ be a matching in a graph $G$. A path $P$ in $G$ is called _$M$
-alternating_ if the edges in $P$ alternate between edges from $M$ and edges
not from $M$.

If an alternating path connects two unmatched vertexes of $G$, then it is
called _$M$ -augmenting_. An $M$-augmenting path $P$ can be used to improve
the matching $M$; namely by deleting all the edges of $P$ in $M$ and adding
the remaining edges of $P$, we obtain a new matching $M^{\prime}$ with more
edges. This construction implies the following:

8.1. Observation. Assume $G$ is a graph and $M$ is a maximal matching in $G$.
Then $G$ has no $M$-augmenting paths.

On the diagrams we denote the edges in $M$ by solid lines and the remaining
edges by dashed lines.

8.2. Exercise. Find an augmenting path for the matching on the diagram and use
it to construct a larger matching.

Recall that _bigraph_ stands for _bipartite graph_.

8.3. Exercise. Let $M$ be a matching in a bigraph $G$. Show that any
$M$-augmenting path connects vertexes from the opposite parts of $G$.

The following theorem states that the converse to the observation.

8.4. Theorem. Assume $M$ is a matching in a graph $G$. If $M$ is not maximal,
then $G$ contains an $M$-augmenting path.

This theorem implies that Hungarian algorithm [18, Section 7.2] produces a
maximal matching. Indeed, the Hungarian algorithm checks all $M$-alternating
paths in the graph and it will find an $M$-augmenting path if it exists. Once
it is found it could be used to improve the matching $M$. Therefore, by the
theorem, Hungarian algorithm improves any nonmaximal matching; in other words,
it can stop only at a maximal matching.

Proof. Suppose $M$ is nonmaximal matching; that is, there is a matching
$M^{\prime}$ with lager number of edges. Consider the subgraph $H$ of $G$
formed by all edges in $M$ and $M^{\prime}$.

Note that each component of $H$ is either an $M$-alternating path or a cycle.
Each cycle in $H$ has the same number of edges from $M$ and $M^{\prime}$.
Since $|M^{\prime}|>|M|$, the one component of $H$ has to be a path that
starts and ends by an edge in $M^{\prime}$. Evidently such path is
$M$-augmenting. ∎

### Marriage theorem

Assume that $G$ is a graph and $S$ is a set of its vertexes. We say that a
matching $M$ of $G$ _covers_ $S$ if any vertex in $S$ is incident to an edge
in $M$.

Given a set of vertexes $W$ in a graph $G$, the set $W^{\prime}$ of all
vertexes adjacent to at least one of vertexes in $W$ will be called the _set
of neighbors_ of $W$. Note that if $G$ is a bigraph and $W$ lies in the left
part, then $W^{\prime}$ lies in the right part.

8.5. Marriage theorem. Let $G$ be a bigraph with the left and right parts $L$
and $R$. Then $G$ has a matching which covers $L$ if and only if for any
subset $W\subset L$ the set $W^{\prime}\subset R$ of all neighbors of $W$
contains at least as many vertexes as $W$; that is,

$|W^{\prime}|\geqslant|W|.$

Proof. Assume that a matching $M$ is covering $L$. Note that for any set
$W\subset L$, the set $W^{\prime}$ of its neighbors includes the vertexes
matched with $W$. In particular,

$|W^{\prime}|\geqslant|W|;$

it proves the ‘‘only if’’ part.

Consider a maximal matching $M$ of $G$. To prove the ‘‘if’’ part, it is
sufficient to show that $M$ covers $L$. Arguing by contradiction, assume that
there is a vertex $w$ in $L$ which is not incident to any edge in $M$.

Consider the maximal set $S$ of vertexes in $G$ which are reachable from $w$
by $M$-alternating paths. Denote by $W$ and $W^{\prime}$ the set of left and
right vertexes in $S$ correspondingly.

Since $S$ is maximal, $W^{\prime}$ is the set of neighbors of $W$. According
to Observation 8, the matching $M$ provides a bijection between $W-w$ and
$W^{\prime}$. In particular,

$|W|=|W^{\prime}|+1;$

the latter contradicts the assumption. ∎

8.6. Exercise. Assume $G$ is an $r$-regular bigraph; $r\geqslant 1$. Show that

  1. (a)

$G$ admits a 1-factor;

  2. (b)

the edge chromatic number of $G$ is $r$; in other words, $G$ can be decomposed
into $1$-factors.

Remark. If $r=2^{n}$ for an integer $n\geqslant 1$, then $G$ in the exercise
above has an Euler’s circuit. Note that the total number of edges in $G$ is
even, so we can delete all odd edges from the circuit. The obtained graph
$G^{\prime}$ is regular with degree $2^{n-1}$. Repeating the described
procedure recursively $n$ times, we will end up at a 1-factor of $G$.

There is a tricky way to make this idea work for arbitrary $r$, not
necessarily a power of $2$; it was discovered by Noga Alon [see alon and also
kalai].

In Exercise 8 one has to assume that $G$ is bipartite. Indeed, the following
exercise states that the graph on the diagram has no 1-factor, while it is
3-regular.

8.7. Exercise. Prove that the graph shown on the diagram has no 1-factor.

8.8. Exercise. Children from 25 countries, 10 kids from each, decided to stand
in a rectangular formation with 25 rows of 10 children in each row. Show that
you can always choose one child from each row so that all 25 of them will be
from different countries.

8.9. Exercise. The sons of the king divided the kingdom between each other
into 23 parts of equal area — one for each son. Later a new son was born. The
king proposed a new subdivision into 24 equal parts and gave one of the parts
to the newborn son.

Show that each of 23 older sons can choose a part of land in the new
subdivision which overlaps with his old part.

8.10. Exercise. A table $n{\times}n$ is filled with nonnegative numbers.
Assume that the sum in each column and each row is 1. Show that one can choose
$n$ cells with positive numbers which do not share columns and rows.

8.11. Advanced exercise. In a group of people, for some fixed $s$ and any $k$,
any $k$ girls like at least $k-s$ boys in total. Show that then all but $s$
girls may get married to the boys they like.

### Vertex covers

A set $S$ of vertexes in a graph is called a _vertex cover_ if any edge is
incident to at least one of the vertexes in $S$.

8.12. Theorem. In any bigraph, the number of edges in a maximal matching
equals the number of vertexes in a minimal vertex cover.

It is instructive to do the following exercise before reading the proof.

8.13. Exercise. Let $M$ be a maximal matching in a bigraph $G$. Assume two
unmatched vertexes $l$ and $r$ lie on the opposite parts of $G$. Show that no
pair of $M$-alternating paths starting from $l$ and $r$ can have a common
vertex.

On the following diagram, a maximal matching is marked by solid lines; the
remaining edges of the graph are marked by dashed lines. The vertexes of the
cover are marked in black and the remaining vertexes in white; the unmatched
vertexes are marked by a cross.

Proof. Fix a bigraph $G$; denote by $L$ and $R$ its left and right parts. Let
$M$ be a matching and $S$ be a vertex cover in $G$.

By the definition of vertex cover, any edge $m$ in $M$ is incident to at least
one vertex in $S$. Therefore

$|S|\geqslant|M|.$

That is, the number of vertexes in any vertex cover $S$ is at least as large
as the number of edges in any matching $M$.

Now assume that $M$ is a maximal matching. Let us construct a vertex cover $S$
such that $|S|=\nobreak|M|$.

Denote by $U_{L}$ and $U_{R}$ the set of left and right unmatched vertexes
(these are marked by cross on the diagram). Denote by $Q_{L}$ and $Q_{R}$ the
set of vertexes in $G$ which can be reached by $M$-alternating paths starting
from $U_{L}$ and from $U_{R}$ correspondingly.

Note that $Q_{L}$ and $Q_{R}$ do not overlap. Otherwise there would be an
$M$-augmenting path from $U_{L}$ to $U_{R}$ (compare to Exercise 8). Therefore
$M$ is not maximal — a contradiction.

Further note that if $m$ is an edge in $M$, then both of its end vertexes lie
either in $Q_{L}$ or $Q_{R}$, or neither.

Let us construct the set $S$ by taking one incident vertex (left or right) of
each edge $m$ in $M$ by the following rule: _if $m$ connects vertexes in
$Q_{L}$, then include its right vertex in $S$; otherwise include its left
vertex_. Since $S$ has exactly one vertex incident to each edge of $M$, we
have

$|S|=|M|.$

It remains to prove that $S$ is a vertex cover; that is, at least one vertex
of any edge $e$ in $G$ is in $S$.

Note that if the left vertex of $e$ lies in $Q_{L}$, then $e$ is an edge on an
$M$-alternating path starting from $U_{L}$. Therefore the right vertex of $e$
also lies in $Q_{L}$.

Therefore it is sufficient to consider only the following three cases:

  * $\diamond$

The edge $e$ has its right vertex in $Q_{L}$ and its left vertex outside of
$Q_{L}$. In this case, both vertexes of $e$ lie in $S$.

  * $\diamond$

The edge $e$ connects vertexes in $Q_{L}$. In this case, the right vertex of
$e$ is in $S$.

  * $\diamond$

The edge $e$ connects vertexes outside of $Q_{L}$. In this case, the left
vertex of $e$ is in $S$. ∎

8.14. Exercise. A few squares on a chessboard are marked. Show that the
minimal number of rows and columns that cover all marked squares is the same
as the maximal number of rooks on the marked squares that do not threaten each
other.

### Edge cover

A collection of edges $N$ in a graph is called an _edge cover_ if every vertex
is incident with at least one of the edges in $N$.

On the diagram, two edge covers of the same graph are marked in solid lines.

8.15. Theorem. Let $G$ be a connected graph with $p$ vertexes and $p>1$.
Assume that a minimal edge cover $N$ of $G$ contains $n$ edges, and a maximal
matching $M$ of $G$ contains $m$ edges. Then

$m+n=p.$

The following exercise will guide you thru the proof.

8.16. Exercise. Suppose $G$, $N$, $M$, $p$, $n$, and $m$ are as in the
theorem. Denote by $m^{\prime}$ the the number of components in $N$.

  1. (a)

Show that $N$ contains no paths of length 3 and no triangle. Conclude that
each component of $N$ is a _star_ ; that is, it is isomorphic to $K_{1,k}$ for
some $k$. Use it to show that

$m^{\prime}+n=p.$

  2. (b)

Choose $m^{\prime}$ edges, one in each component of $N$. Observe that it is a
matching. Conclude that $m^{\prime}\leqslant m$. Use a to show that

$m+n\geqslant p.$

  3. (c)

Consider a subgraph $H$ of $G$ formed by all edges in the matching $M$ and one
edge incident to each unmatched vertex in $G$. Observe that $H$ is a vertex
cover with $p-m$ edges. Conclude that

$m+n\leqslant p.$

  4. (d)

Observe that b and c imply the theorem.

### Minimal cut

Recall that a _directed graph_ (or briefly a _digraph_) is a graph, where the
edges have a direction associated with them; that is, an edge in a digraph is
defined as an _ordered_ pair of vertexes.

8.17. Min-cut theorem. Let $G$ be a digraph. Fix vertexes $s$ and $t$ in $G$.
Then the maximal number of oriented paths from $s$ to $t$ which do not have
common edges equals to the minimal number of edges one can remove from $G$ so
that there will be no oriented path from $s$ to $t$.

Proof. Denote by $m$ the maximal number of oriented paths from $s$ to $t$
which do not have common edges. Denote by $n$ the minimal number of edges one
can remove from $G$ to disconnect $t$ from $s$; more precisely, after removing
$n$ edges from $G$, there will be no oriented path from $s$ to $t$.

Let $P_{1},\dots,P_{m}$ be a maximal collection of oriented paths from $s$ to
$t$ which have no common edges. Note that in order to disconnected $t$ from
$s$, we have to cut at least one edge in each path $P_{1},\dots,P_{m}$. In
particular, $n\geqslant m$.

Consider the new orientation on $G$ where each path $P_{i}$ is oriented
backwards — from $t$ to $s$.

Consider the set $S$ of the vertexes which are reachable from $s$ by oriented
paths for this new orientation.

Assume $S$ contains $t$; that is, there is a path $Q$ from $s$ to $t$, which
can move along $P_{i}$ only backwards.

(Further, the path $Q$ will be used the same way as the augmenting path in the
proof of the marriage theorem. In a sequence of moves, we will improve the
collection $Q,P_{1},\dots,P_{m}$ so that there will be no overlaps. On the
diagram, a case with $m=1$ that requires two moves is shown; $P_{1}$ is marked
by a solid line and $Q$ is marked by a dashed line.)

Since $P_{1},\dots,P_{m}$ is a maximal collection, $Q$ overlaps with some of
the paths $P_{1},\dots,P_{m}$. Without loss of generality, we can assume that
$Q$ first overlaps with $P_{1}$ — assume it meets $P_{1}$ at the vertex $v$
and leaves it at the vertex $w$. Let us modify the paths $Q$ and $P_{1}$ the
following way: Instead of the path $P_{1}$ consider the path $P_{1}^{\prime}$
that goes along $Q$ from $s$ to $v$ and after that goes along $P_{1}$ to $t$.
Instead of the path $Q$, consider the trail $Q^{\prime}$ which goes along
$P_{1}$ from $s$ to $w$ and after that goes along $Q$ to $t$.

If the constructed trail $Q^{\prime}$ is not a path (that is, if $Q^{\prime}$
visits some vertexes several times), then we can discard some circuits from
$Q^{\prime}$ to obtain a genuine path, which we will still denote by
$Q^{\prime}$.

Note that the obtained collection of paths
$Q^{\prime},P_{1}^{\prime},P_{2}\dots,P_{m}$ satisfies the same conditions as
the original collection. Further, since we discard the part of $P_{1}$ from
$w$ to $v$, the total number of edges in
$Q^{\prime},P_{1}^{\prime},P_{2}\dots,P_{m}$ is smaller than in the original
collection $Q,P_{1},P_{2}\dots\nobreak,P_{m}$. Therefore, by repeating the
described procedure several times, we get $m+1$ paths without overlaps — a
contradiction.

It follows that $S\not\ni t$.

Note that all edges which connect $S$ to the remaining vertexes of $G$ are
oriented toward to $S$. That is, every such edge which comes out of $S$ in the
original orientation belongs to one of the paths $P_{1},\dots,P_{m}$.

Moreover, for each path $P_{i}$ there is only one such edge. In other words,
if a path $P_{i}$ leaves $S$, then it can not come back. Otherwise $S$ could
be made larger by moving backwards along $P_{i}$. Therefore cutting one such
edge in each path $P_{1},\dots,P_{m}$ makes it impossible to leave $S$. In
particular, we can disconnect $t$ from $s$ by cutting $m$ edges from $G$; that
is, $n\leqslant m$. ∎

Remark. The described process has the following physical interpretation. Think
of each path $P_{1},\dots,P_{m}$, and $Q$ like water pipelines from $s$ to
$t$.

At each overlap of $Q$ with another path $P_{i}$, the water in $P_{i}$ and $Q$
runs the opposite directions. So we can cut the overlapping edges and
reconnect the open ends of the pipes to each other while keeping the water
flow from $s$ to $t$ unchanged. As the result, we get $m+1$ pipes form $s$ to
$t$ with no common edges and possibly some cycles which we can discard. An
example of this procedure for two paths $P_{1}$ and $Q$ is shown on the
diagram; as above, $P_{1}$ is marked by a solid line and $Q$ is marked by a
dashed line.

8.18. Advanced exercise. Assume $G$ is a bigraph. Let us add two vertexes, $s$
and $t$, to $G$ so that $s$ is connected to each vertex in the left part of
$G$, and $t$ is connected to each vertex in the right part of $G$. Orient the
graph from left to right. Denote the obtained digraph by $\hat{G}$.

Give another proof of the marriage theorem for a bigraph $G$, applying the
min-cut theorem to the digraph $\hat{G}$.

### Remarks

The marriage theorem was proved by Philip Hall in [16]; it has many
applications in all branches of mathematics. The theorem on vertex cover was
discovered by Dénes Kőnig [25], and rediscovered by Jenő Egerváry [7]. The
theorem on min-cut was proved by Peter Elias, Amiel Feinstein, and Claude
Shannon [8], it was rediscovered by Lester Ford and Delbert Fulkerson [11].

These theorems form a base for the Hungarian algorithm that solves the
_assignment problem_ ; see page $\diamond$ ‣ 7. This algorithm was found by
Harold Kuhn, but (as it was discovered by François Ollivier) essentially the
same algorithm was found much earlier by Carl Gustav Jacobi [28].

An extensive overview of the marriage theorem and its relatives is given by
Alexandr Evnin in [9].

##  Chapter 9 Toroidal graphs

Recall that a graph is called _planar_ if it can be drawn on a plane with no
crossings; the latter is equivalent to the existence of its drawing on a
sphere. Here and further, we say _drawing_ for _drawing with no crossings_.

In this chapter we will discuss drawing of graphs on a torus — another surface
that can be obtained by revolving a circle about an axis (this is the surface
of a donut).

A graph is called _toroidal_ , if it can be drawn on a torus with no crossing.

If one cuts a torus along a parallel and a meridian as shown on the diagram,
then the obtained surface can be developed into a square.111Formally speaking
it means that there is a continuous map $f\colon\square\to T$ from a square to
torus such that $f(x)=f(y)$ if and only if $x=y$ or $x$ and $y$ are
corresponding points on the opposite sides of the square. It gives a
convenient way to describe drawings of graphs on the torus which will be
called _square diagram_. One only has to remember that the corresponding
points on opposite sides of the square are identified in the torus; in
particular, all four vertexes of the square correspond to one point in the
torus.

For example, on the given square diagram you see a drawing of the complete
graph $K_{5}$; in particular it shows that $K_{5}$ is toroidal. Note that the
edge $xy$, after coming to the right side of the square, reappears at the
corresponding point of the left side and goes further to $y$. Similarly, the
edge $vw$ comes to the top and reappears at the bottom. At these points, the
edges cross the parallel and the meridian.

The following square diagrams show that $K_{4,4}$ and $K_{7}$ are toroidal
graphs as well.

$K_{4,4}$

$K_{7}$

9.1. Exercise. Show that any graph with crossing number 1 is toroidal. That
is, if a graph admits a drawing on a sphere with one crossing, then it admits
a drawing on a torus with no crossings.

9.2. Exercise. Show that each of the following graphs is toroidal; construct a
corresponding square diagram in each case.

(a)  (b)  (c)

### Simple regions

Choose a drawing $G$ of a pseudograph on a torus or sphere; it subdivides the
the surface into regions. A region $R$ is called _simple_ if its interior can
be parameterized by an open plane disc.222Formally speaking it means that the
there is a continuous bijection from interior of $R$ to an open disc in the
plane such that its inverse is also continuous.

The annulus shown on the diagram is an example of a nonsimple region. On a
sphere it may appear only in drawings of nonconnected graphs. That is, if a
drawing of a pseudograph $G$ on a sphere has a nonsimple region, then $G$ is
not connected. This statement should be intuitively obvious, but the proof is
not trivial.

Drawings of connected graphs on a torus may have nonsimple regions. For
example, in the first drawing of $K_{4}$ below,

$p=4$, $q=6$, $r=3$; the regions $B$, $C$ are simple, and $A$ is not.

$p=4$, $q=6$, $r=2$; both regions $D$ and $E$ are simple.

the regions $B$ and $C$ are simple and the region $A$ is not (it contains the
meridian of the torus). The second drawing of $K_{4}$ has only two regions,
$D$ and $E$, and both of them are simple.

Further we will use the following claim which should be intuitively obvious.
We do not present its proof, but it is not hard; a reader familiar with
topology may consider it as an exercise.

9.3. Claim. Let $G$ be a drawing of a pseudograph on a torus or sphere and $R$
its simple region. Suppose that a drawing $G^{\prime}$ obtained from $G$ by
adding a new edge $e$ in the region $R$.

  1. (a)

If both of vertexes of $e$ are in $G$ (the edge $e$ might be a loop), then $e$
divides $R$ into two simple regions.

  2. (b)

If only one of vertexes of $e$ are in $G$, then $e$ does not divide $R$ and
the corresponding region of $G^{\prime}$ is simple.

9.4. Advanced exercise. Suppose that $G$ is a drawing of a connected nonlanar
graph on the torus. Show that each region of $G$ is simple.

### Euler’s formula

9.5. Theorem. For any drawing $G$ of a connected pseudograph on the torus we
have

$p-q+r\geqslant 0,$

where $p$, $q$, and $r$ denote the number of vertexes, edges and regions in
$G$ respectively.

Moreover, equality holds if all regions of $G$ are simple.

Note that the inequality might be strict. For example, for the first drawing
of $K_{4}$ above we have

$p-q+r=4-6+3=1>0.$

It happens since the region $A$ is not simple. For the second drawing of
$K_{4}$ we have the equality

$p-q+r=4-6+2=0,$

as it is supposed to be by the second part of the theorem.

In the proof we will use the following lemma which is a simple corollary of
Claim 9. Given a drawing of pseudograph $G$ with $p$ vertexes, $q$ edges and
$r$ regions, set

$\Sigma_{G}=p-q+r.$

9.6. Lemma. Let $G$ be a drawing of a pseudograph on a torus or sphere.
Suppose that another drawing $G^{\prime}$ of a connected pseudograph that is
obtained from $G$ by adding a new edge $e$. Then

$\Sigma_{G^{\prime}}\leqslant\Sigma_{G}.$ ➊

Moreover, if all regions of $G$ are simple, then

  1. (a)

we have equality in ➊ ‣ 9 and

  2. (b)

all regions of $G^{\prime}$ are simple as well.

Proof. Since $G^{\prime}$ is connected, one of the ends of $e$ belongs to $G$.
Denote by $R$ the region of $G$ that contains $e$.

If the other end of $e$ is not in $G$, then $e$ does not divide its region. In
this case $G^{\prime}$ has an extra vertex and an extra edge, and the number
of regions did not change; that is, $p^{\prime}=p+1$, $q^{\prime}=q+1$, and
$r^{\prime}=r$. Therefore

$\Sigma_{G^{\prime}}=p^{\prime}-q^{\prime}+r^{\prime}=p-q+r=\Sigma_{G}.$

If the other end of $e$ is in $G$, then $e$ may divide $R$ in two regions or
may not divide it. According to Claim 9, the latter may happen only if $R$ is
not simple. Note that after adding $e$, the number of vertexes did not change.
That is, $p^{\prime}=p$, $q^{\prime}=q+1$, $r^{\prime}\leqslant r+1$ and the
equality holds if $R$ is simple. Therefore

$\Sigma_{G^{\prime}}=p^{\prime}-q^{\prime}+r^{\prime}\leqslant
p-q+r=\Sigma_{G}$

and the equality holds if $R$ is simple.

According to Claim 9, if $R$ is simple, then the region(s) of $G^{\prime}$
that correspond to $R$ are simple as well. The rest of the regions did not
change. Hence b follows. ∎

Proof of 9. We need to show that

$\Sigma_{G}\leqslant 0$ ➋

for any drawing of connected pseudograph $G$ on the torus $T$.

Let $H$ be a drawing of the pseudograph formed by one meridian and one
parallel as shown. Note that it has 1 vertex, 2 edges and 1 region; therefore

$\Sigma_{H}=1-2+1=0.$ ➌

Without loss of generality, we may assume that the edges of $G$ and $H$
intersect and have only a finite number of points of intersection. The latter
can be achieved by perturbing the drawing of $G$.

Let us subdivide the graphs $G$ and $H$ by adding a new vertex at every
crossing point of the graphs. The obtained graphs, say $\bar{G}$ and
$\bar{H}$, are subgraphs of a bigger graph, say $W$, formed by all edges and
vertexes of $\bar{G}$ and $\bar{H}$. Note that adding a vertex on an edge
increases the number of vertexes and edges by $1$ and the number of regions
stays the same. Since the subdivision is obtained by adding a finite number of
extra vertexes, we get that

$\Sigma_{G}=\Sigma_{\bar{G}}\quad\text{and}\quad\Sigma_{H}=\Sigma_{\bar{H}}.$
➍

By construction, $W$ is connected. If $W\neq G$, then there is an edge $e$ of
$W$ that is not in $G$, but has one of its ends in $G$. By adding $e$ to $G$
and applying the procedure recursively, we will obtain $W$ in a finite number
of steps. Applying Lemma 9 at each step, we get

$\Sigma_{W}\leqslant\Sigma_{\bar{G}}.$ ➎

Analogously, $W$ can be obtained from $H$ in a finite number of steps by
adding one edge at a time. Since the only region of $H$ is simple, the
obtained drawings will have only simple regions. Therefore, applying Lemma 9
at each step, we get

$\Sigma_{W}=\Sigma_{\bar{H}}.$ ➏

Finally ➌ ‣ 9, ➍ ‣ 9, ➎ ‣ 9, and ➏ ‣ 9 imply ➋ ‣ 9; indeed

$\Sigma_{G}=\Sigma_{\bar{G}}\geqslant\Sigma_{W}=\Sigma_{\bar{H}}=\Sigma_{H}=0.$

∎

9.7. Exercise. Suppose that $G$ is a toroidal graph with girth at least $4$.
Show that

$q\leqslant 2{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}p,$

where $p$ and $q$ denote number of vertexes and edges in $G$.

9.8. Exercise. Is there a drawing of $K_{5}$ on torus with only square
regions? If ‘‘yes’’, then draw a square diagram; if ‘‘no’’, explain why.

### The seven color theorem

9.9. Theorem. The chromatic number of any toroidal graph can not exceed $7$.

Recall that $K_{7}$ is toroidal; see the diagram on page 9. Therefore the
theorem gives an optimal bound. In the proof, we will use the following lemma,
which is a simple corollary of Euler’s formula (9).

9.10. Lemma. Let $G$ be a toroidal graph with $p$ vertexes and $q$ edges. Then

$q\leqslant 3{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}p.$

Proof. Choose a drawing of $G$ on a torus. By Euler’s inequality we have

$p-q+r\geqslant 0,$

where $r$ denotes the number of regions in the drawing.

Note that each region in the drawing has at least $3$ sides and each edge of
$G$ appears twice as a side of a region. Therefore

$3{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}r\leqslant 2{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}q.$

These two inequalities imply the corollary. ∎

Proof of 9. Suppose that there is a toroidal graph $G$ that requires $8$
colors. Choose a critical subgraph $H$ in $G$ with chromatic number 8. Denote
by $p$ and $q$ the number of vertexes and edges in $H$.

By [18, Theorem 2.1.3], each vertex in $H$ has degree of at least $7$. By the
handshake lemma [18, Theorem 1.1.1], we have

$7{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}p\leqslant 2{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}q.$

On the other hand, by Lemma 9, we have

$q\leqslant 3{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}p.$

These two inequalities contradict each other. ∎

### A remark about forbidden minors

It is straightforward to see that if $G$ is toroidal, then any graph obtained
from $G$ by deletion of a vertex or an edge or by contracting an edge is also
toroidal.

A graph that can be obtained from a given graph $G$ by applying a sequence of
such operations is called a _minior_ of $G$. The pseudograph $G$ is considered
to be a minor of itself. The other minors require at least one deletion or
contraction; they are called _proper minors_.

Note that the statement above implies that any minor of a toroidal graph is
toroidal, or in other words, _toridality is inherited to minors_.

The following deep result was proved by Neil Robertson and Paul Seymour [33].

9.11. Theorem. Any property of pseudographs that is inherited to minors can be
described by a finite set of _forbidden minors_ ; that is, a pseudograph meets
the property if and only if none of its minors are forbidden.

For example, note that deletion and contraction do not create cycles; that is,