Introduction to graph theory and basic algorithms

Mikhail Tuzhilin∗; Dong Zhang†

This book collects the lectures about graph theory and its applications which were given
to students of mathematical departments of Moscow State University and Peking University.
Graph theory is a very wide field with a lot of applications in almost every scientific area:
in many branches of mathematics, computer science, physics, chemistry, biology and also in
psychology, arts, philosophy and many others. Nowadays, graph theory becomes especially
more important because of the rapid development of molecular biology, neural networks and
arXiv:2312.11543v2 [[Link]] 13 Oct 2024

AI fields. One of the aims of writing this book was to give students thorough knowledge about
graphs to understand modern scientific fields more deeply. Here we tried to give classical and
modern theorems and algorithms in more understandable and simple way. We spent many time
to rewrite them and close the gaps in several “simplest” well-known proofs to provide more
precise and accurate material for students.
The book starts with the basic definitions and assumptions which are required for the further
material and slowly increases the complexity. Note that the book’s narrative is sequential:
earlier theorems and definitions are used in later material. After theoretical parts usually goes
the part with algorithms and examples. The last three sections are highly connected with
modern fields such as Social Network Analysis and Spectral Graph Theory.
The first author wrote Sections 1-14 and 15.1, and the second author, Dong Zhang, wrote
Sections 15.2, 15.3 and 16. We would like to thank Sino-Russian mathematical center and
especially professor Fan Huijun for assistance and attention to our work. We acknowledge
support from National Key R and D Program of China (Grant No. 2020YFE0204200).

Contents
1 Basic definitions 3

2 Two matrices corresponded to a graph 6

2.1 Adjacency matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 Incidence matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

3 Connectivity and trees 7

4 Spanning trees and algorithms 9

4.1 Spanning trees of unweighted graphs . . . . . . . . . . . . . . . . . . . . . . . . 9
4.2 Minimal spanning trees of weighted graphs . . . . . . . . . . . . . . . . . . . . . 11

5 Laplacian matrix and Kirchhoff ’s theorem 12

6 Bipartite graph 16

7 Shortest path problems 18

∗
Affiliation: Moscow State University, Electronic address: mtu93@[Link]
†
Affiliation: Peking University, Electronic address: dongzhang@[Link];

1
8 Planar graph and polyhedrons 22
8.1 Planar graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
8.2 Polyhedrons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

9 K-connectivity 27
9.1 κ-vertex and λ-edge connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . 27
9.2 Bridge detecting algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

10 2-connectivity 30
10.1 Eulerian graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
10.2 Hamiltonian graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

11 Planarity and κ-connectivity 36

11.1 Planarity testing algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
11.2 3-connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
11.3 4-connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

12 Duality 42
12.1 Dual graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
12.2 Steinitz theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
12.3 Dual polyhedrons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
12.4 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

13 Flows on graphs 55
13.1 Decomposition of flows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
13.2 Max-flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
13.3 Proof of Menger’s theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
13.4 Minimum-cost flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

14 Local and global characteristics of graph 64

14.1 Centralities with local knowledge . . . . . . . . . . . . . . . . . . . . . . . . . . 64
14.2 Centralities with global knowledge . . . . . . . . . . . . . . . . . . . . . . . . . . 68

15 Spectral properties 70
15.1 Adjacency and Laplacian matrix spectrum . . . . . . . . . . . . . . . . . . . . . 71
15.2 The normalized Laplacian spectrum . . . . . . . . . . . . . . . . . . . . . . . . . 74
15.3 Cheeger inequality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

16 Graph p-Laplacian 82
16.1 Unnormalized version of the p-Laplacian eigenproblem . . . . . . . . . . . . . . 83
16.2 Normalized p-Laplacian eigenvalue problem . . . . . . . . . . . . . . . . . . . . 86

References 88

2
1 Basic definitions
Definition 1.1. A set of pairs of any objects is called graph G = (V, E), where
V (vertices, or nodes, or points) — the set current of objects,
E (edges) — the set of pairs.
NB! In this book the vertex set is considered as finite V ⊂ N. Also we denote by graph (n, m)
a graph with n vertices and m edges.
Definition 1.2. A graph is called (un)directed iff. the set of pairs is (un)directed set respec-
tively.
Example 1.1. Consider a graph of the cube:

V = {1, 2, 3, 4, 5, 6, 7, 8},

E = (1, 2), (1, 4), (1, 5), (2, 6), (2, 3),
(3, 7), (3, 4), (5, 6), (5, 8), (6, 7), (7, 8) .

Figure 1: Cube graph representation.

Definition 1.3. Two vertices i, j in undirected graph connected with an edge are called ad-
jacent and are denoted by i ∼ j.
Definition 1.4. An edge that consists of the same elements is called loop.
Definition 1.5. A subset of edges that consists of the same elements is called multiple edges
(or multi-edge).
Example 1.2.
(1, 1) — loop,
{(1, 2), (1, 2), (1, 2)} — multiple edges.
NB! Now and further we will consider only simple graphs — graphs without loops and mul-
tiple edges unless otherwise specified.

NB! There is important difference between simple directed graph and simple undirected graph.
Be aware of the case {(1, 2), (2, 1)}.
Definition 1.6. Directed graph is called oriented graph if there are no two-side edges between
any two vertices of the graph.
Definition 1.7. Subgraph is the part of the graph that is a graph.
NB! In the definition of graph we don’t include isolated vertices. This definition can be
expanded by adding the set of vertices to edges, but this or similar definitions will give rise
many problems further so we omit this case.
Definition 1.8. Induced subgraph on the current subset vertices of a graph is the maximal
by inclusion of edges subgraph whose set of vertices is the current set.
Definition 1.9. Two graphs are called isomorphic if one can re-number the vertices of one
graph to obtain another.

3
 Figure 2: Example of isomorphism.

Figure 3: Example of non-isomorphic graphs.

Figure 4: Are these graphs isomorphic or not?

4
Remark 1.1. To prove that two graphs in figure 3 are non-isomorphic compare the structures
of their induced subgraphs.
It is simple to prove the graph isomorphism in special cases like in figure 3 but in general
this proof is NP-hardness problem. Try to solve the problem in figure 4.

NB! Isomorphic graphs are also called the same graphs.

Definition 1.10. Degree of vertex vi (deg vi ) is the number of edges which are coming out
from the vertex vi .

Definition 1.11. A graph is called regular iff. all vertices have equal degrees.

In different books and articles definition of degree may vary: it can be defined by the number
of in-edges and also by total edges (sum of in- and out-edges), but here we use the out-edges
definition.

Definition 1.12. A vertex is called even (odd) if it has even (odd) degree.

Lemma 1. (Handshaking lemma).

X
deg vi = 2∥E∥.
vi ∈V
P
Proof. Note that in vi ∈V deg vi every edge occurs 2 times.

Example 1.3. Consider the bit representation of natural numbers

from 0 to 2n − 1. Let’s Define the graph of n-dimensional cube by
following:

1. V = {i for i from 0 to 2n − 1},

2. E = {(i,j) iff. i and j differ only in one bit}.

How many edges have n-dimensional cube for any n?

The simplest cases n = 1, 2, 3 are well-known: it is segment,
square and cube with 1, 4 and 12 edges respectively.
For another cases let’s use Handshaking lemma:

deg vi = ∥V ∥ deg vi = n 2n .
P
2∥E∥ = vi ∈V

Thus ∥E∥ = n 2n−1 .

Figure 5: Graphs of hypercubes.

Definition 1.13. Path is the sequence of edges in which ending and beginning vertices of
consecutive edges are coincide.

Definition 1.14. Graph is called weighted if each edge eij corresponds to a number wij ∈ R.

One can consider edges with zero weight but this correspondence may lead to many problems
in further definitions and algorithms e.g. adjacency matrix, incidence matrix and so on thus
we suppose that wij ̸= 0 for i, j ∈ V . Also sometimes we will denote a vertex vi by i for short.

5
2 Two matrices corresponded to a graph
2.1 Adjacency matrix
Definition 2.1. Adjacency matrix A(G) for unweighted directed graph G is defined by
following:
(
1 if there exists edge from vertex vi to vertex vj ,
A(G) = {aij } :=
0 otherwise.
NB! For weighted directed graph adjacency matrix (or weight adjacency matrix ) can be defined
in the same way by replacing 1’s by a weight wij for each edge eij .

Figure 6: Example of a directed graph and its weight adjacency matrix.

Properties of adjacency matrix:

1. Adjacency matrix is symmetrical for undirected graph,
2. Adjacency matrix diagonal elements equal to 0 (no loops),
3. Adjacency matrix always square matrix,
4. For unweighted graph adjacency matrix consists of 0 and 1 and
deg vi = {the sum elements in i row of adjacency matrix},

5. “Adjacence” correspondence between weighted directed graphs and matrices with prop-
erties 2-3 is one-to-one if 0 weights are excluded.
Theorem 1. The number of paths from vertex vi to vj of length k is equal to (A(G)k )ij for any
unweighted graph G.
Proof. Let’s consider the induction by the length k:
1. The number of paths from vertex vi to vj of the length 1 corresponds to existence of
the edge eij . (
1 if there is edge from vertex vr to vj ,
{arj } =
0 otherwise.
2. Suppose the induction statement holds for any given k, then
X
(Ak+1 )ij = (Ak )ir arj = {Number of paths from vertex vi to vr with length k}*
vr ∈V

*{1 if there is edge from vr to vj , 0 — overwise} =

= {Number of paths from vertex vi to vj of length k + 1}.

6
2.2 Incidence matrix
Consider unweighted directed graph G with some numeration of edges.

Definition 2.2. Incidence matrix for unweighted directed graph G and its edges numeration
is defined by following:

1
 if edge j starts from vertex vi ,
B(G) = {bij } = −1 if edge j ends in vertex vi , .

0 otherwise.


NB! For unweighted undirected graph incidence matrix can be defined equivalently, but in-
stead of all -1’s will be 1’s.

NB! To generalize incidence matrix definition for weighted graphs (or weighted incidence ma-
trix) multiply each column by weight of corresponding edge.

Figure 7: Example of graph and its weight incidence matrix.

Properties of incidence matrix:

1. In each column of incidence matrix there are only two non-zero elements,

2. Incidence matrix is rectangular matrix with dimensions ∥V ∥ × ∥E∥,

3. The sum of elements in each incidence matrix column equals to 0 for directed graphs,

4. For unweighted undirected graph incidence matrix consists of 0 and 1 and

deg vi = {the sum of elements in i row of incidence matrix},

5. “Incidence” correspondence between weighted directed graphs and matrices with proper-
ties 2-4 is one-to-one up to column permutations if non-positive weights are excluded.

3 Connectivity and trees

Definition 3.1. Graph is called connected iff. there exists path between any two vertices.

Definition 3.2. Connected component of a graph is connected subgraph that is not part
of any larger connected subgraph.

7
 For directed graph there exist several connectivity definitions: weakly connectivity (if re-
placing of directed edges to undirected edges produces a connected undirected graph), semi-
connectivity (if there exists one-side path between any two vertices) and strong connectivity
(if there exists path between any two vertices from one to another and vise versa). For each
of these connectivity one can define corresponded connected components, but we will consider
properties and prove theorems only for undirected case here and in the next section.

Let’s consider some simplest necessary and sufficient conditions of connectivity.

Lemma 2 (Odd vertices lemma). The number of odd vertices in each connected component of
undirected graph is even.

Proof. Use Handshaking lemma for each connected component.

Theorem 2. (Connectivity necessary condition). Consider an undirected graph G(n, m). If

2
m > Cn−1 , then graph G is connected.

Proof. Assume the contrary: there exist greater or equal than two connected components.
Denote one component by G1 and all the rest by G2 . Hence, G = G1 ⊔ G2 .
Consider two cases:
2
1. Let ∥V (G1 )∥ = n − 1, ∥V (G2 )∥ = 1 =⇒ ∥E(G)∥ = ∥E(G1 )∥ ≤ Cn−1 — the maximum
number of edges in undirected graph with n − 1 vertices.
The same for ∥V (G1 )∥ = 1, ∥V (G2 )∥ = n − 1.

2. Let 2 ≤ ∥V (G1 )∥ = m ≤ n − 2 =⇒

2 2 2m2 + n2 − 2nm − n 2 n2 − 3n + 2
∥E(G)∥ = ∥E(G1 )∥+∥E(G2 )∥ ≤ Cm +Cn−m = ∨Cn−1 =
2 2
n − 1 + m2 − nm ∨ 0
(m − 1)(m − n + 1) ≤ 0
2
This gives a contradiction, since ∥E(G)∥ > Cn−1 .

Definition 3.3. Cycle is a path consisted from distinct edges where the first and last vertices
coincide.

Definition 3.4. Simple path is a path where any edges and vertices are distinct except the
first and the last vertices.

Definition 3.5. Simple cycle is a simple path where the first and last vertices coincide.

Lemma 3. A graph contains a cycle iff. it contains a simple cycle.

Proof. 1. If a graph contains a simple cycle then it obviously contains a cycle.

2. Consider a graph that contains a cycle. Let’s construct a simple cycle: start from any
vertex of the cycle and walk through the cycle and delete visited edges. Since the cycle
is finite, some visited vertex will be reached after several steps. The cycle corresponded
to this walk to the first visited vertex is simple cycle.

8
Definition 3.6. Tree is undirected connected acyclic (without cycles) graph.

Another definition of tree holds from the lemma 3: tree is undirected connected graph with-
out simple cycles.

Definition 3.7. Polytree is an oriented graph whose underling undirected graph is a tree.

Definition 3.8. Tree leaf is a vertex of degree 1.

Definition 3.9. Tree root is any highlighted vertex of the graph.

NB! The root is any highlighted vertex of the graph, however the leafs, in general, are not
highlighted as roots.

Definition 3.10. Arborescence of a directed graph is the polytree that consist of all vertices
of the graph that can be reached from the root.

Lemma 4 (Two leafs lemma). Every tree contains two leafs.

Proof. The method is the same as in previous lemma. Let’s start walking from any vertex
and deleting visited edges. Since the graph is finite, a dead end will be reached after several
steps. The end corresponds to first leaf. Starting this procedure again from the leaf will
provide the second.

Lemma 5 (Uniqueness path lemma). There exists unique path between any two vertices of tree.

Proof. Hint: assume the contrary and find cycle.

4 Spanning trees and algorithms

4.1 Spanning trees of unweighted graphs
Definition 4.1. Spanning tree of undirected graph is a tree that contains all vertices of a
graph.

NB! Spanning trees exist only for undirected connected graphs. For not connected graph there
is another definition — spanning forest — the collection of spanning trees corresponded to each
connected component.

Consider the base algorithms for constructing spanning trees:

1. Depth-first search (DFS) is the algorithm for searching elements in tree-structured

data. Here we discuss it from constructing spanning trees point of view.
Description:

(a) Start from the root. The root is assigned first number.
(b) Walk through non-assigned vertices and assign visited vertices by consecutive num-
bers (from second) as long as you can continue.
(c) If it is dead end, return to the previous vertex and do the step 1b.

9
 The assigned numbers form depth-first order.

To construct spanning tree, you should save edges on the step 1b from previous assigned
vertex to the new one that has to be assigned (see figure 8).
2. Breadth-first search (BFS) is also the algorithm for searching elements in tree-
structured data. Here we discuss it from constructing spanning trees point of view.
Description:
(a) Start from the root. The root is assigned first number.
(b) Assign all non-assigned adjacent vertices by consecutive numbers (from second).
(c) Go to the next (up to assigning) not visited vertex and do the step 2b.
The assigned numbers form breadth-first order.

To construct spanning tree, you should save edges on the step 2b from the current vertex
to new non-assigned vertices which have to be assigned (see figure 8).


NB! It is easy to see, that the complexity of these algorithms equals to O ∥V∥ + ∥E∥ .

Figure 8: Depth-first search (left) and breadth-first search (right) algorithms, orders and cor-
responding spanning trees (red).

In general situation depth-first search and breadth-first search algorithms produce different
spanning trees. Spanning tree from depth-first search algorithm is called Trémaux tree, while
from breadth-first search just breadth-first tree. Also there is a freedom to choose a walking
direction and thus different directions produce different spanning trees as well.
For not connected graphs these algorithms also can be used. In this case they will construct
spanning trees for the connected component of the root. By changing root between components
one can construct spanning trees for each component so-called spanning forest.

NB! These algorithms can by applied for checking connectivity condition of the graph.
Theorem 3 (Necessary and sufficient tree condition 1). A graph with n vertices is tree iff. it
is connected and consists of n − 1 edges.
Proof.
1. Necessarity. Consider the induction by the number of vertices:
(a) For graph (1, 0) holds.
(b) Let for every tree with n vertices the condition holds. Consider tree T with n + 1
vertices. This tree contains two leafs by two leafs lemma 4. By deleting one of
these leafs the graph will become a tree T ′ with n vertices and edges decreased by
1. The tree T ′ consists of n − 1 edges by inductive hypothesis, therefore T consists
of n edges.

10
 2. Sufficiency. Construct the spanning tree of the graph by one of algorithms above. The
spanning tree consists of n − 1 edges.

Theorem 4 (Necessary and sufficient tree condition 2). A graph with n vertices is tree iff. it
is acyclic and consists of n − 1 edges.

Proof.

1. Necessarity. Holds from theorem 3.

2. Sufficiency. Let the number of connected components be k. Construct the spanning

tree for every component. Each component is tree, therefore the total number of edges
in the graph equals n − k (−1 for every component) =⇒ k = 1 and the graph is
connected.

NB! By these theorems, the complexity of depth-first search

and breadth-first

search algorithms
for connected graphs can be rewritten as O ∥V∥ + ∥E∥ = O ∥E∥ .

4.2 Minimal spanning trees of weighted graphs

For weighted graph there exists another type of spanning tree:

Definition 4.2. Minimal spanning tree is the spanning tree with minimum total edge
weight.

Consider two basic algorithms for constructing minimal spanning tree. These algorithms
belong to large area called greedy algorithms (in which making the locally optimal choice at
each stage leads to globally optimal solution).

1. Prim’s algorithm.
Description:

(a) Start from arbitrarily vertex. This vertex is the tree T .

(b) Let the K(T ) — edges ̸∈ T adjacent to any vertex ∈ T . Add to the tree T new
edge with minimum weight in K(T ) that is not produce the cycle in T and vertices
incident to this edge.
(c) Do 1b step ∥V ∥ − 1 times.

2. Kruskal’s algorithm.
Description:

(a) Start from arbitrarily vertex. This vertex is the tree T .

(b) Let the K(T ) — all edges ̸∈ T . Add to the tree T new edge with minimum weight
in K(T ) that is not produce the cycle in T and vertices incident to this edge.
(c) Do 2b step ∥V ∥ − 1 times.


NB! The Prim’s and Kruskal’s algorithms complexity is O ∥E∥ log(∥V∥) .

Minimal spanning trees from Prim’s and Kruskal’s algorithms depend of the first selected
vertex and also of edges from the equal weights subset.

11
Remark 4.1. The proof of correctness Prim’s and Kruskal’s algorithms holds from theorem 3
and theorem 4 respectively or from greedy property.
Each of these algorithms has its pros and cons: Prim’s algorithm producesconnected graph


for each step but binary heap and adjacency list should be used to reach O ∥E∥ log ∥V ∥
complexity. Kruskal’s algorithm reach this complexity by using simpler structures.

5 Laplacian matrix and Kirchhoff ’s theorem

As in previous two sections let’s consider undirected unweighted graph G.

Definition 5.1. Laplacian matrix (also called Kirchhoff matrix) for undirected un-
weighted graph G is defined by following:

deg vi if i = j,

L(G) = {lij } = −1 if there exists edge from vertex vi to vertex vj ,

0 otherwise.


Or equivalently:
L(G) = Diag{deg vi | vi ∈ V } − A(G).

Figure 9: Example of a graph and its laplacian matrix.

Properties of Laplacian matrix:

1. Laplacian matrix non-diagonal part consists of 0 and -1 elements,

2. Laplacian matrix is symmetrical matrix,

3. Laplacian matrix is square matrix,

4. The sum of elements in each Laplacian matrix column (and row) equals to 0,

5. Laplacian matrix is degenerate matrix,

6. “Laplacian” correspondence between undirected unweighted graphs and matrices with

properties 1-4 is one-to-one.

Lemma 6 (Laplacian matrix algebraic complements lemma). Algebraic complements of all

Laplacian matrix elements are equal.

Proof. Denote the number of vertices of a graph G by n and the algebraic complement to
the element lij of Laplacian matrix by Lij . Consider two cases:

12


1. Let rk L(G) < n − 1 =⇒ Lij = 0, for any i, j.


2. rk L(G) = n − 1. Let’s denote the column of all 1’s by j, the matrix of complements
{Lij } by M and the columns of M T by {mj }. Hence, Lj = 0 due to Laplacian matrix
property 4 and

LM T = det(L) · I = 0 =⇒ Lmj = 0, for j = 1, 2, ..., n.

Consider a linear equation Lx = 0. Since the rk L(G) = n − 1, solutions of the
equation form a one-dimensional linear space. The vector j is a solution of the equation,
hence all other solutions (m1 , m2 , ..., mn ) are proportional to j and therefore consist of
equal elements. From the symmetry property of the Laplacian matrix the proposition
holds.

Lemma 7 (Laplacian and incidence matrix lemma). L = B B T , where B is the incidence

matrix for any orientation of the graph and numeration of the edges.

Proof. Consider any orientation and numeration of the edges of undirected graph and let
B be its corresponding incidence matrix. Denote the row i of the matrix B by bi and the
number of vertices of the graph by n.

B B T = {mij } = {bi · bj }.

1. For i = j, mii = b2i = {the number of non-zero elements in bi } =

= {the sum of elements in i row in the incidence matrix for undirected graph} = deg vi ,
due to incidence matrix property 4.

2. For i ̸= j, (
−1 if vi adjacent to vj by the edge k,
bik bjk = .
0 otherwise.
Since the graph has no loops,
n
X
mij = bi · bj = bik bjk = lij .
k=1

Lemma 8 (Graph (n, n − 1) lemma). Let B(G) — the incidence matrix for some orientation
and numeration edges of the graph G(n, n − 1) and D(B) be maximal principal minor of the
matrix B. It follows, that

1. D(B) = ±1, if G is connected (tree),

2. D(B) = 0, if G is not connected (not tree).

Proof. 1. Let the graph G be connected. The graph G is tree by the theorem 3 and
therefore it has at least two leafs by lemma 4.
For the graph G(n, n−1) the matrix B(G) is also n×(n−1) matrix, hence the maximal
principal minor is the determinant of matrix B(G) without some row. Suppose that
this row corresponds to last vertex vn without loss of generality (if it is not re-number
vertices).

13
 (a) Consider the leaf ̸= vn and the edge adjacent to the leaf. Re-number vertices and
edges such that this leaf becomes first vertex v1 and its adjacent edge becomes
the first edge e1 . This re-numbering procedure corresponds to row and column
permutations in the matrix B(G) and in the determinant D(B), therefore D(B)
is not changing. By this re-numbering the first row of the matrix B(G) becomes
equal to (±1, 0, 0, ..., 0).
(b) Consider the induced subgraph on V (G)\{v1 } vertices and do the same procedure
as in 1a for this subgraph. Thus, the corresponding vertex and the edge become the
second vertex and the second edge and the second row of the matrix B(G) become
to look like (∗, ±1, 0, 0, ..., 0), where “*” means some number. Let’s continue this
procedure.
(c)  
±1 0 0 ... 0
 ∗ ±1 0 ... 0 
 
∗ ∗ ±1 ... 0 
In the end, the matrix B(G) become to look like  , and

 ... 

∗ ∗ ∗ ... ±1
∗ ∗ ∗ ... ∗
D(B) will be the determinant of the upper part of the matrix. Therefore, D(B) =
±1.
2. Suppose the graph G is not connected. Denote by G1 the connected component without
vertex vn and G2 all the rest.
Consider the sub-matrix K ⊂ B(G) corresponding to vertices of G1 . The incidence
matrix B(G1 ) is the sub-matrix of the matrix K. The sum in each column of the
matrix K equals to 0. Indeed, if edge belongs to G1 then the sum equals to 0 by
property 3 of incidence matrix B(G1 ) and if edge belongs to G2 then all elements in
corresponding column equals 0. Hence, the sum of rows of the matrix K equals 0. Since
K is the part of the matrix corresponding to D(B), the determinant D(B) = 0.

Theorem 5 (Kirchhoff matrix tree theorem). The number of trees in undirected unweighted
connected graph G equals to an algebraic complement of any Laplacian matrix element.
Proof. From Lemma 7: L(G) = B B T . Let’s denote the number of vertices of graph G by n.
Algebraic complements of all Laplacian matrix elements are equal by the lemma 6. Consider
the algebraic complement Lnn of the last bottom-right element lnn . Let’s denote B̂ the matrix
B(G) without last row. Therefore, Lnn = B̂ B̂ T .
Since the graph is connected, the number of edges is ≥ n − 1 and hence the principal
minor D(B̂) of the matrix B̂ has (n − 1) × (n − 1) dimensions. Let T (B) be the sub-matrix
of B consisted of the columns corresponding to D(B̂) (see Figure 10). The sub-matrix T (B)
is obtained by adding to D(B̂) last row and hence has n × (n − 1) dimensions. Therefore, the
sub-matrix T (B) corresponds to a subgraph Ĝ(n, n − 1) ⊂ G. Moreover, this matrix equals
to incidence matrix of the subgraph B(Ĝ) (to prove this part more accurately, one should
either consider the definition of subgraph with isolated vertices or prove this part in terms
of sub-matrices). By the lemma 8:
(


±1 if Ĝ is tree,
D T (B) = D B(Ĝ) = ,
0 if it is not,

and it is also equal to D(B̂).

14
 Figure 10: Designations in the Kirchhoff matrix theorem proof.

The last step is to use a formula from algebra:

Lemma (Binet-Cauchy formula). Consider the matrix equation:
P × Q = C
s×t t×s s×s
for two rectangular matrices P and Q of s × t and t × s dimensions and square s × s matrix
C for any s, t ∈ N.
Let the columns of matrix P be called “corresponded” to rows of matrix Q iff. they are
consist of the same sets of indexes. Denote the minors consisted of the corresponding columns
and rows by Pi1 i2 ...is and Qi1 i2 ...is respectively, for indexes i1 , i2 , ..., is ∈ {1...t} with repetitions.
It follows that
X t
det C = Pi1 i2 ...is Qi1 i2 ...is
i1 ,i2 ,...,is =1

Proof. The complete proof won’t be provided here, just the main ideas:
1. For case s = t, it is well-known determinant of two matrices product: det (P Q) =
det P det Q.
2. For case s > t, the determinants Pi1 i2 ...is and Qi1 i2 ...is = 0 for any i1 i2 ...is because of
repetitions and rk(P Q) ≤ rk(P ) ≤ t =⇒ det C = 0.
3. For case s < t, it follows from two algebraic facts:
(a) The coefficient of z t−k in the polynomial det (zIt + C) is the sum of the k × k
principal minors of C for any k = 1, 2, .., t, where It is the identity matrix of
t × t dimensions.
(b) If s ≤ t, then det (zIt + Q P ) = z t−s det (zIs + P Q), for matrices P and Q from
the statement.

Using the Binet-Cauchy formula for matrices Lnn = B̂ B̂ T :

X X X
B̂i1 i2 ...in−1 B̂iT1 i2 ...in−1 = Di21 i2 ...in−1 (B̂) = D2 B(Ĝ) ,


Lnn =
i1 ,i2 ,...,in−1 i1 ,i2 ,...,in−1 Ĝ(n,n−1)⊂G

and by the lemma 8 it equals to the number of spanning trees of G.

15
Definition 5.2. The complete graph Kn is the graph where any two vertices are connected
with an edge.

Theorem 6 (Cayley’s formula). The number of spanning trees of the complete graph Kn equals
to nn−2 .

Proof. The Laplacian matrix for the complete graph Kn is

 
n − 1 −1 −1 ... −1
 −1 n − 1 −1 ... −1 
L(G) =  ,
 ... 
−1 −1 ... −1 n − 1

of dimensions n × n.
The algebraic complement to the last element lnn is the determinant of the matrix of
dimensions (n − 1) × (n − 1). Let’s find this algebraic complement.
   
n − 1 −1 −1 ... −1 1 1 1 ... 1
 −1 n − 1 −1 ... −1  −1 n − 1 −1 ... −1 
Lnn = det   adding all =
rows to first
det  =
 ...   ... 
−1 −1 ... −1 n − 1 −1 −1 ... −1 n − 1
 
1 1 1 ... 1
adding first row to others  0 n 0 ... 0 
 = nn−2 .
= det 
 ... 
0 0 ... 0 n

6 Bipartite graph
Definition 6.1. Connected undirected graph is called bipartite iff. one can divide the vertices
into two groups such that any two vertices from one group are not adjacent.

Consider the bipartite property testing algorithm:

1. Choose any vertex.

2. Start depth-first or breadth-first algorithms and divide vertices to 0 or 1 groups by putting

to them corresponded marks:

(a) For depth-first: sequentially alternate marks for depth-first walk.

(b) For breadth-first: put the same marks if the vertices are on the same breadth and
change marks otherwise.

3. If any two vertices from one group are not adjacent, the graph is bipartite and not bipartite
otherwise.

NB! The complexity of this algorithm is the
same as for depth-first and breadth-first algorithms
for connected graphs and equals to O ∥E∥ .

16
Example 6.1. Consider the result of the testing algorithm:

Figure 11: Group division (red marks) by depth-first algorithm (left) and breadth-first algo-
rithm (right).

This graph is not bipartite because after the algorithm there are adjacent vertices from the
same group.
Theorem 7 (Necessary and sufficient bipartite condition). Connected undirected graph is bi-
partite iff. it doesn’t contain odd length cycles.
Proof.
1. Necessarity. Assume the contrary: the graph contains odd length cycle. Let’s start to
divide vertices from this cycle to two groups by the rule: two vertices from one group
should not be adjacent. By this rule vertices will sequentially alternate to each other.
Since the length of cycle is odd, the first and the last vertices will be from the same
group. This gives a contradiction with bipartite condition.

2. Sufficiency. Consider bipartite property testing algorithm with spanning tree T con-
struction. It is easy to see that any tree is a bipartite graph. Let’s start to add
remaining edges. Denote first edge by (v, w).
Assume that vertices v and w corresponds to the same group by the testing algorithm.
By the lemma 5 there exists unique path from v to w in T . Since the marks alternate
to each other along this path by the algorithm, this path with the edge (v, w) form
an odd length cycle. This gives a contradiction. Hence, all remaining edges connect
vertices from different groups.

Definition 6.2. Bipartite graph is called complete bipartite graph Kn,m iff. any two
vertices from different groups are connected with an edge.
Theorem 8 (Cayley’s formula for bipartite graphs). The number of spanning trees of the
complete bipartite graph Kn,m equals to nm−1 mn−1 .
Proof. The Laplacian matrix for the complete bipartite graph consists of 4 blocks:
 
m 0 0 ... 0 −1 −1 ... −1 −1
 0 m 0 ... 0 −1 −1 ... −1 −1
 

 ... ... 

0 0 ... 0 m −1 −1 ... −1 −1 
L(G) = −1 −1 ... −1 −1 n
.
 0 0 ... 0  
−1 −1 ... −1 −1 0 n 0 ... 0 
 
 ... ... 
−1 −1 ... −1 −1 0 0 ... 0 n

17
 The first upper-left corner with m’s has n × n dimensions and the last lower-right corner
with n’s has m × m dimensions.
The algebraic complement to the last element lnn is the determinant of the matrix of
dimensions (n + m − 1) × (n + m − 1). Let’s find this algebraic complement.
 
m 0 0 ... 0 −1 −1 ... −1 −1
 0 m 0 ... 0 −1 −1 ... −1 −1
 

 ... ... 

0 0 ... 0 m −1 −1 ... −1 −1 adding all rows to first
Lnn = det 
−1 −1 ... −1 −1 n
 =
 0 0 ... 0  
−1 −1 ... −1 −1 0 n 0 ... 0 
 
 ... ... 
−1 −1 ... −1 −1 0 0 ... 0 n
 
1 1 1 ... 1 0 0 ... 0 0
 0 m 0 ... 0 −1 −1 ... −1 −1
 

 ... ... 

0 0 ... 0 m −1 −1 ... −1 −1 to the last m − 1’s
 adding first row =
= det 

−1 −1 ... −1 −1 n 0 0 ... 0  
−1 −1 ... −1 −1 0 n 0 ... 0 
 
 ... ... 
−1 −1 ... −1 −1 0 0 ... 0 n
 
1 1 1 ... 1 0 0 ... 0 0
0 m 0 ... 0 −1 −1 ... −1 −1
 

 ... ... 

0 0 ... 0 m −1 −1 ... −1 −1
= det   = mn−1 nm−1 .
0 0 ... 0 0 n 0 0 ... 0 
 
0 0 ... 0 0 0 n 0 ... 0 
 
 ... ... 
0 0 ... 0 0 0 0 ... 0 n

There is also more general definition of complete k-partite graph. We will consider such
graphs in the subsection 15.2. For these graphs it is easy to reformulate and proove this Cayley’s
theorem by analogy for more general case.

7 Shortest path problems

In this section there will be observed the basic algorithms of searching shortest path between
vertices for weighted directed or undirected graphs.
Definition 7.1. A cycle in weighted graph is called negative cycle if the sum of weights
along the cycle is negative.
If the path between two vertices intersects negative cycle, the shortest path between them
is not exist. Therefore, for shortest path algorithms we consider only graphs without negative
cycles unless otherwise specified.
These algorithms are very similar for both directed and undirected cases, so let’s give
combined definition:
Definition 7.2. Spanning tree of weighted (directed) undirected graph G is called (shortest
path arborescence) shortest path tree if the path from the root to any other vertex along
the (poly)tree is the shortest path in G.

18
Consider basic algorithms:
1. Dijkstra’s algorithm.
This algorithm finds the shortest path tree (shortest path arborescence) with selected
vertex as a root for (directed) undirected graphs with positive weights.
Description:
(a) Initialization: mark all vertices unvisited, initialize two arrays: d[v] — array of
minimum distances and p[v] — array of predecessors for shortest paths from the
root to vertices v and assign d[v] by zero for the selected vertex and infinities for all
the rest.
(b) Find the unvisited vertex v with the smallest value in d. For each its unvisided
neighbour w if the sum of d[v] plus weight of the edge (v, w) is less than value d[w],
change d[w] to the sum and change the predecessor p[w] for v. After checking all
unvisited neighbours mark v as visited.
(c) If there exist unvisited vertices in the graph go to 1b.
Edges (predecessors and corresponded vertices) form shortest path tree (see figure 12).

NB! The complexity of Dijkstra’s algorithm equals to O ∥E∥ + ∥V∥2 =  O ∥V∥2 in the 


simplest realization. Using binary search tree or binary heap it equals to O ∥E∥ + ∥V∥ log ∥V∥ .

Figure 12: Shortest path tree (left, red) and sequential steps of Dijkstra’s algorithm (right).
The root vertex of the shortest path tree is denoted by “*”. Underlined numbers corresponded
to visited vertices.

2. Bellman–Ford algorithm.
This algorithm is similar to Dijkstra’s algorithm. It finds the (shortest path arborescence)
shortest path tree with selected vertex as a root for any (directed) undirected graphs.
Description:
(a) Initialize two arrays: d[v] — array of minimum distances and p[v] — array of pre-
decessors for shortest paths from the root to vertices v and assign d[v] by zero for
the selected vertex and infinities for all the rest.
(b) For each edge (v, w) if the sum of d[v] plus weight of the edge (v, w) is less than
value d[w], change d[w] to the sum and change the predecessor p[w] for v.

19
 (c) Do case 2b ∥V ∥ − 1 times.

Edges (predecessors and corresponded vertices) form shortest path tree similar to Dijk-
stra’s algorithm (see figure 13).

NB! The complexity of Bellman–Ford algorithm equals to O ∥V∥ ∥E∥ .

Figure 13: Shortest path arborescence (left, red), the edge set of the graph (right-top) and
sequential steps of Bellman–Ford algorithm (right-bottom). The root vertex of the shortest
path arborescence is denoted by “*”.

NB! Dijkstra’s and Bellman–Ford algorithms are also used for searching shortest path
between two selected vertices for directed and undirected weighted graphs (walk along
predecessors in reverse order to find the shortest path). Also, Dijkstra’s algorithm can be
stopped earlier when the final vertex was visited and Bellman–Ford algorithm when the
minimum distances array was not changed.

Bellman–Ford algorithm also finds negative cycle in a graph. If the graph contains
negative cycle, the shortest path between any two vertices of the cycle doesn’t exist and if
one runs the algorithm one more time (∥V ∥ times in total) the minimum distances array
will change. Let’s consider this algorithm (see figure 14 for example):

(a) Do case 2b one more time.

(b) Find the vertex v, where d[v] was changed.
(c) The negative cycle is obtained by saving vertices from this vertex v along precursors
array at previous ∥V ∥-1 step (in reverse order).

20
Figure 14: Sequential steps of Bellman–Ford algorithm (right) for the graph (left). The starting
vertex is denoted by “*”. Column (vertex) D with underlined number corresponds to the value
that have changed at the additional ∥V ∥ step. The negative cycle DCBD is constructed by
walking along precursors set (in reverse order) from this vertex.

3. Floyd–Warshall algorithm.
This algorithm finds the shortest path matrix d[v][w] (shortest path between any two
vertices) for a graph.
Description:

(a) Initialize shortest path matrix d[v][w]: for every edge (v, w) the element d[v][w] is
equal to the weight of (v, w) and ∞ otherwise.
(b) For each vertex w check for each pair of vertices v, u if the sum of d[v][w] and d[w][u]
is less than d[v][u]. If it is then change d[v][u] for this sum.


NB! The complexity of Floyd–Warshall algorithm equals to O ∥V∥3 .

4. Johnson’s algorithm.
This algorithm finds the shortest path matrix for a graph by using Bellman–Ford shortest
path tree and Dijkstra’s algorithm for weighted undirected connected graph and for di-
rected graph if there exist paths from the root to any other vertex (spanning arborescence,
see figure 15 for example).
Description:

(a) Use Bellman–Ford algorithm, calculate the minimum distances array d[v] and check
if the graph contains negative cycle.
(b) If the graph doesn’t contain negative cycle, correct all weights using Bellman–Ford’s
values: change the weight of each edge (v, w) to the sum of the weight and d[v]−d[w].
(c) For each vertex use Dijkstra’s algorithm and calculate shortest path matrix.
(d) Correct shortest path matrix by reverse transformation: change each d[v][w] to the
difference between d[v][w] and d[v] − d[w].


NB! The complexity of Johnson’s algorithm equals to O ∥V∥ ∥E∥ + ∥E∥ + ∥V∥ ∥V∥ log∥V∥ =


O ∥E∥ + ∥V∥ ∥V∥ log∥V∥ .
After changing the weights of the graph at the step 4b all weights become non-negative
with zero-weights along Bellman–Ford’s arborescence. Using Dijkstra’s algorithm for each
vertex it gives zero shortest path along the arborescence.

21
Figure 15: First two steps of Johnson’s algorithm (top). Minimum distances lengths d[v] for
the first step are written near vertices in brackets. Weights of edges were changed at the second
step. Shortest path matrix for the graph with new weights by using Dijkstra’s algorithm (right-
bottom). Result shortest path matrix (left-bottom).

8 Planar graph and polyhedrons

8.1 Planar graph
Definition 8.1. A graph is called planar iff. there exists representation of the graph without
intersections of edges.
Example 8.1. 1. Every tree is planar.

2. K2 , K3 , K4 are planar.

3. K5 is not planar.

4. K1,2 , K1,3 , K2,2 , K2,3 are planar.

5. K3,3 is not planar.

Proof. 1. It is easy to see that tree is planar (use depth-first or breadth-first orders to
prove it).

2. Just try to draw these graphs on plane without intersections.

3. To prove that K5 is not planar let’s use classical theorem:

Theorem (Jordan curve). Any simple closed curve C divides the plane for two disjoint
open subsets and any curve starting from a point of the first subset and ending in a
point of the second subset intersect C.

These subsets are denoted by int(C) — inner subset and out(C) — outer subset.
Consider the contrary. The cycle C = v1 v2 v3 v1 is closed curve thus it divides the plane
by two parts. Let’s suppose without loss of generality that v4 ∈ int(C). Consider three

22
 cycles C1 = v2 v3 v4 v2 , C2 = v3 v4 v1 v3 , C3 = v1 v2 v4 v1 . Since vi ∈ out(Ci ), the assumption
that v5 ∈ int(Ci ) gives contradiction (the edge (v5 , vi ) should intersect Ci by Jordan
curve theorem) and therefore, v5 ∈ out(Ci ) for i = 1, 2, 3. Hence, v5 ∈ out(C) =
T3
out(Ci ) and it gives contradiction because v4 ∈ int(C).
i=1

4. K1,2 , K1,3 are trees. For K2,2 , K2,3 just draw this graph on plane without intersections.

5. Use the same procedure like in 3.

Definition 8.2. Inner face of the planar graph is the inner int(C) part of the plane bounded
by a simple cycle C of graph.
Definition 8.3. Outer face of the planar
T graph is the common outer part out(G) for all
simple cycles Ci of graph G : out(G) = out(Ci ).
i

Notations: The set of all faces (inner and outer) is denoted by F .

NB! Any tree has only one outer face and no inner faces.
Theorem 9 (Euler). For any planar connected graph holds

∥V ∥ − ∥E∥ + ∥F ∥ = 2.

Proof. Use the induction by number of faces k = ∥F ∥:

1. If graph contains only one face (k = 1), this face should be outer face. If there are no
inner faces then there are no cycles in the graph and therefore graph is tree. For tree
∥V ∥ = n, ∥E∥ = n − 1 and the condition holds.

2. Let for any planar connected graph with k faces condition holds. Consider a planar
connected graph with k + 1 faces. Since the graph is planar, there exists an edge
(without intersections with any other edges) that separates the outer face and some
inner face. If one delete this edge the number of faces will decrease at 1 and hence the
formula will be satisfied. Therefore, the condition holds for the initial graph also.

Corollary 1. Let c be the number of connected components of a planar graph. Then the formula
holds:
∥V ∥ − ∥E∥ + ∥F ∥ = 1 + c.
Proof. Hint: for each connected component H : ∥V (H)∥−∥E(H)∥+∥F (H)∥ = outer face+1.

Corollary 2. For a connected planar graph ∥E∥ ≤ 3∥V ∥ − 6.

Proof. Consider some representation of our planar graph G (e.g. use Auslander-Parter algo-
rithm in subsection 11.1). For this representation every face corresponds to a simple cycle
and consists of ≥ 3 edges and every edge belongs to a boundary of two different faces. Hence,
for the graph G : 2∥E∥ ≥ 3∥F ∥. By the Euler’s theorem:

3∥F ∥ = 6 − 3∥V ∥ + 3∥E∥ ≤ 2∥E∥ =⇒ ∥E∥ ≤ 3∥V ∥ − 6.

23
Corollary 3. Every connected planar graph has a vertex of degree at most five.
Proof. Assume the contrary: all vertices
P have degrees greater or equal than six. By Hand-
shaking lemma 6∥V ∥ − 12 ≥ 2∥E∥ = vi ∈V deg vi ≥ 6∥V ∥ holds contradiction.

Let’s consider some operations of a planar graphs which preserve the planarity:
Lemma 9. Every subgraph of a planar graph is planar.
Proof. Holds from the definition.

Definition 8.4. Subdivision of an edge is an operation when the edge is replaced by a path
of the length two: the internal vertex is added to the graph.
Lemma 10. Every subdivision of the non-planar graph is non-planar.
Proof. Just consider the inverse operation.

By these two lemma’s we can easy prove the necessary condition of one of the most important
theorem about planar graphs:
Theorem (Pontryagin-Kuratowski). A connected graph is planar iff. it doesn’t contain subdi-
visions of complete graphs K5 and K3,3 .
We will provide the full proof of this theorem in section 11.

8.2 Polyhedrons
Definition 8.5. Polyhedron is a set of polygons such that
1. Each side of a polygon should be the side of one another polygon,

2. The intersection of any two polygons can be just either edge of vertex,

3. There exists path through polygons between any two polygons.

Let’s introduce another theorem like Jordan curve theorem for hyper-surfaces in Rn :
Theorem (Jordan-Brouwer). Any connected compact simple hypersurface S n−1 divides Rn for
two disjoint open subsets and any curve starting from point of the first subset and ending in a
point of the second subset intersect S n−1 .
We can consider each polyhedron P like 2-dimensional surface in R3 and thus it divides
the 3-dimensional space by two disjoint parts inner int(P ) and outer out(P ). The boundary of
polyhedron is denoted by ∂(P ).
Definition 8.6. Polyhedron is said to be convex iff. the edge from any point of polyhedron
to any inner point doesn’t intersect the polyhedron.
This definition can be reformulate as any point of polyhedron is visible from any inner point.
Theorem 10 (Euler for convex polyhedrons). For convex polyhedrons the following holds:

∥V ∥ − ∥E∥ + ∥F ∥ = 2,

where V, E and F are vertices, edges and faces of polyhedron respectively.

24
 Proof. By the convex definition there exists the bijection from polyhedron to a sphere around
this polyhedron with the center in inner point. By this bijection the graph of polyhedron
G(P ) is mapped to the graph on the sphere G′ with the same number of vertices, edges and
faces. Consider the stereographic projection from the sphere with the center inside some
face Fi of graph G′ to the 2-dimensional plane. This graph G′ maps bijectively (because of
stereographic projection property, see figure 16) to the graph on the plane G′′ such that inner
faces of G′ except Fi maps to inner faces of G′′ and Fi maps to the outer face of G′′ . It is easy
to see that the graph G′′ is planar (consider contrary and use bijections properties) with the
same number of vertices, edges and faces. Therefore by using Euler theorem for the graph
G′′ the condition holds.

Figure 16: Two bijections from Euler’s theorem about convex polyhedrons.

Corollary 4. For any face of a planar graph there exists the representation where this face is
outer face.

Proof. Let’s use the stereographic projection like in the theroem 10 two times. First, let’s
project the planar graph from the plane to sphere using inverse stereographic projection with
any center. Second, choose the center of second stereographic projection inside the chosen
face. By the composition of these projections this face becomes outer face.

Since the Euler theorem holds for polyhedrons, upper estimation ∥E∥ ≤ 3∥V ∥−6 also holds.
Let’s give lower estimation for polyhedrons. Since the intersection of any two polygons can be
just either edge or vertex, any vertex degree must be ≥ 3. Therefore, by using Handshaking
lemma 2∥E∥ ≥ 3∥V ∥ and thus, 1.5∥V ∥ ≤ ∥E∥ ≤ 3∥V ∥ − 6 holds for polyhedrons.

Definition 8.7. Platonic solid is a convex polyhedron, that consists of the same regular
polygons and the vertices have the same degrees.

Example 8.2. Let’s n be the number of vertices of polygons of a platonic solid and deg be degree
of any vertex. The following holds for platonic solids:

n∥F ∥ = deg∥V ∥ = 2∥E∥.

Let’s multiply Euler formula on 2n and use the equation before.

2 n∥V ∥ − 2 n∥E∥ + 2 n∥F ∥ = 4 n,

25
 2 n∥V ∥ − n deg∥V ∥ + 2 deg∥V ∥ = 4 n,


∥V ∥ 2 n − deg (n − 2) = 4 n.
The number n > 0 and ∥V ∥ > 0, thus 2 n − deg (n − 2) > 0 and therefore, (n − 2) deg < 2 n.
Let’s use this equation and this estimation to classify all platonic solids (see figure 17). Let’s
also note that the minimum number of n = 3 and the minimum degree deg = 3:
1. n = 3 =⇒ deg < 6,
(a) deg = 3 =⇒ ∥V ∥ = 4. This platonic solid is called Tetrahedron.
(b) deg = 4 =⇒ ∥V ∥ = 6. This platonic solid is called Octahedron.
(c) deg = 5 =⇒ ∥V ∥ = 12. This platonic solid is called Icosahedron.
2. n = 4 =⇒ 2 deg < 8 =⇒ deg < 4,
(a) deg = 3 =⇒ ∥V ∥ = 8. This platonic solid is called Cube.
3. n = 5 =⇒ 3 deg < 10 =⇒ deg < 4,
(a) deg = 3 =⇒ ∥V ∥ = 20. This platonic solid is called Dodecahedron.
4. n ≥ 6, Let’s use the estimation again:
0 > n deg − 2 deg − 2 n = n (deg − 2) − 2 deg ≥ 4 deg − 12.
This gives the contradiction, since deg ≥ 3.
Using Handshaking lemma and Euler theorem 10 the number of edges and faces can be
found. As a result the full classification is obtained:
Name n deg ∥V ∥ ∥E∥ ∥F ∥
Tetrahedron 3 3 4 6 4
Octahedron 3 4 6 12 8
Icosahedron 3 5 12 30 20
Cube 4 3 8 12 6
Dodecahedron 5 3 20 30 12

Figure 17: All platonic solids: Tetrahedron, Octahedron, Icosahedron (top), Cube, Dodecahe-
dron (bottom).

26
9 K-connectivity
9.1 κ-vertex and λ-edge connectivity
Definition 9.1. A set of vertices (edges) is called k-vertex (edge) cut if a graph becomes
not connected after the deletion of this set.
Definition 9.2. A graph is called κ-vertex (edge) connected iff. it doesn’t have any k − 1-
vertex (edge) cuts.
NB! κ-vertex connectivity is also shortly called κ-connectivity.
Example 9.1. 1. We assume that empty graph and the graph with only one vertex are not
connected.

2. 1-connected graph is just connected.

3. If a graph is k-vertex (edge) connected then it is also k − 1-vertex (edge) connected,

k − 2-vertex (edge) connected and so on.

4. The complete graph Kn is n − 1-vertex and edge connected.

5. The complete bipartite graph Kn,m is min(n, m)-vertex and edge connected.
Definition 9.3. The paths between two vertices are called k-vertex (edge) independent
iff. there exist k paths between these vertices which consist of disjoint sets of vertices (edges).
Consider another example:
Statement 1. Paths between any two vertices of complete graph Kd+1 are d-vertex (edge)
independent.
Proof. Consider two vertices vi , vj . Let’s show d-vertex (edge) independent paths:
1. One path: vi vj .

2. d − 1 paths: vi vk vj , for vk ∈ V \ {vi , vj }.

Theorem (Menger). A graph is κ-vertex (edge) connected iff. for any two vertices there exist
κ-vertex (edge) independent paths.
We will prove this theorem in subsection 13.3. Let’s consider the corollary of this theorem:
Corollary 5. If a graph G is 3-connected then G \ (u, v) is 2-connected for any edge (u, v).
We will use this corollary later. Now let’s consider the relation between vertex and edge
connectivity:
Lemma 11. Let κ(G), λ(G) are numbers of vertex and edge connectivity for a graph G respec-
tively. Let d(G) be the minimum degree. The following holds:

κ(G) ≤ λ(G) ≤ d(G).

Proof.
1. Case κ(G) ≤ λ(G). Since κ(G)-vertex independent paths are also edge independent,
this estimation holds by the Menger’s theorem.

27
 2. Case λ(G) ≤ d(G). By deleting d(G) edges at the vertex with minimum degree the
graph becomes not connected.

Theorem 11 ((κ, λ, d)-graph). For any κ, λ, d ∈ N : κ ≤ λ ≤ d, there exists a graph with κ

— vertex connectivity, λ — edge connectivity and d — minimum degree number.

Proof. Consider two copies G1 , G2 of complete graph Kd+1 . Let’s mark λ vertices in the first
graph G1 and κ vertices in the second G2 . Add λ edges between all marked vertices such
that each marked vertex should be adjacent to some added edge (see figure 18 for example).
Denote the constructed graph by G.

Figure 18: Example of (3, 4, 5)-graph. The red vertices are marked vertices, the red edges are
added edges.

Let’s prove, that the graph G is a graph with κ-vertex connectivity, λ-edge connectivity
and minimum degree d.

1. Since κ ≤ λ < d + 1, there exists unmarked vertex, that remains the same as for
complete graph Kd+1 . Hence the minimum degree of graph G equals d.

2. Let’s prove that the collection of paths between any two vertices of the graph G is κ-
vertex and λ-edge independent. If these vertices belong to the same complete subgraph
Kd+1 then the condition holds from the statement 1. If considered vertices belong
to the different complete subgraphs Kd+1 then let’s consider following paths: first
vertex, any marked vertex from the same subgraph, adjacent marked vertex from the
second subgraph and the second vertex. It is easy to see that they are vertex and
edge independent and the number of paths equals to κ and λ for vertex and edge
independence respectively.
By using Menger’s theorem the proof ends.

9.2 Bridge detecting algorithm

Definition 9.4. An edge of a connected graph is called bridge iff. the graph becomes not
connected after the deletion of this edge.

NB! The bridges can be only in 1-edge connected graphs.

Let’s consider the bridge detecting algorithm:

28
 Tarjan’s algorithm.
For any vertex v let’s denote by DFS[v] — the order of the vertex v, by av — ancestors of
v, by dv — descendants of v corresponding to depth first search algorithm.
Description:

1. Use depth first search algorithm to define DFS order DFS[v] and construct the corre-
sponding spanning tree of the graph.

2. For each vertex v in the reverse DFS order define:


DFS[v],

low[v] := min DFS[av ] if edge (v, av ) doesn’t belong to DFS tree, (1)

low[dv ] if edge (v, dv ) belongs to DFS tree.


3. The edge (v, dv ) is a bridge iff. DFS[v] < low[dv ].

NB! The
complexity of this algorithm is the same as for depth-first search algorithm and equals
to O ∥E∥ for connected graphs.

NB! If one add orientation of the current graph by following: orient DFS tree as Tremaux
arborescence and orient other edges from descendants to ancestors, the low[v] will correspond
to the lowest number in DFS order that can be reached from the vertex v.

Finally, Let’s prove:

Lemma 12. Let the function low[v] is defined by equation 1 for any vertex of a connected graph
G. The edge (v, dv ) is a bridge in G iff. DFS[v] < low[dv ] for a descendant dv of vertex v.

Proof. Let’s denote the set of ancestors of v by Av and the set of descendants of v by Dv .
First let’s note that
S the edge (v, dv ) is a bridge in G iff. this edge divides vertices by two
disjoint sets Av {v} and Dv such that there is no edges between these sets except (v, d).
Also the following holds:

DFS[av ] < DFS[v] < DFS[dv ], ∀av ∈ Av and ∀dv ∈ Dv ,

low[v] ≤ low[dv ], ∀dv ∈ Dv .

1. Necessarity. Let’s prove that DFS[v] < low[dv ] for any descendant dv of vertex v by
induction corresponding to inverse DFS order:

(a) Consider the descendant dv with the highest n = DFS[dv ]. This vertex has
no descendants and only can be adjacent to descendants of v. Since DFS[v] <
DFS[d], ∀d ∈ Dv =⇒ DFS[v] < DFS[adv ] =⇒ DFS[v] < low[dv ].
(b) Let we prove that DFS[v] < low[dv ] for any dv : DFS[dv ] ≥ k. Let’s prove it for
dv : DFS[dv ] = k − 1. For this dv : DFS[v] < DFS[dv ]. Since the vertex dv can only
be adjacent to descendants of v and DFS[v] < DFS[d], ∀d ∈ Dv =⇒ DFS[v] <
DFS[adv ]. By the induction: DFS[v] < low[ddv ]. Therefore, DFS[v] < low[dv ].

2. Sufficiency. Assume the contrary: the edge (v, dv ) is not a bridge. Thus, there exists
an edge (av , d1v ) between two vertices av ∈ Av and d1v ∈ Dv : d1v is descendant of dv .
Thus, low[dv ] ≤ low[d1v ] ≤ DFS[av ] < DFS[v] implies contradiction.

29
Corollary 6. Let the function low[v] is defined by equation 1 for any vertex of a connected
graph G. The edge (v, dv ) is a 1-cut vertex in G iff. DFS[v] ≤ low[dv ] for a descendant dv of
vertex v.

Proof. The proof is the same as in the previous lemma.

NB! By this corollary Tarjan’s algorithm is also can be used for detecting 1-cut vertices and
thus by deleting them one can find all 2-connected components of a graph.

10 2-connectivity
First let’s prove a theorem about outer face of 2-connected planar graph.

Theorem 12. Outer face of 2-connected planar graph G is a simple cycle.

Proof. Consider any planar representation of G. Let’s denote the outer face of G by Cout .
Let’s prove that this Cout contains simple cycle C. Indeed, if one can started a walk by edges
of Cout this walk ends only in a visited vertex (and thus contains simple cycle) otherwise
there previous vertex of this walk will be 1-cut vertex.
Now let’s prove that C = Cout . Assume the contrary: there exists a vertex v ∈ out(C).
Consider any vertex w ∈ C. By Mengers theorem 26 there exist two vertex independent
paths P1 and P2 from w to v. Consider two points x and y — the last points through P1
and P2 respectively such that x, y ∈ C. Let’s denote two vertex independent paths in the
subgraph C from w to x and from w to y by Qwx and Qwy respectively. Let’s denote a parts
of paths PS1 and SP2 from
S x to v and from y to v S by Pxv
and
S PyvS respectively. The cycles
C1 = Qwx Qwy Pxv Pyv and C2 = C \ (Qwx Qwy ) Pxv Pyv are simple cycles by
construction. Since the graph G is planar and C is a simple cycle, either int(C1 ) ⊂ int(C2 ) or
int(C2 ) ⊂ int(C1 ). Thus there exist
T an edge e ∈ C ⊂ Cout such that the curve corresponding
to the edge e is a part of int(C
T 1 ) int(C2 ) in the representation of G. Therefore, this curve
does not intersect out(C1 ) out(C2 ) and it gives contradiction with the definition of Cout .

Let’s consider examples of graphs with 2-connectivity property.

10.1 Eulerian graph

Consider first 2-edge connected graph.

Definition 10.1. Eulerian path is a path that walks through every edge of the graph only
one time.

Definition 10.2. Eulerian cycle is an Eulerian path where the first and the last vertices
coincide.

Definition 10.3. An undirected graph is called Eulerian iff. there exists an Eulerian cycle
in the graph.

Lemma 13. An Eulerian graph is 2-edge connected.

Proof. Assume the contrary: there exists a bridge e in a graph G such that G \ e has at
least two connected components. Hence, if there exists Eulerian cycle it should starting and
therefore ending in the same component. This holds the contradiction.

30
Theorem 13 (Necessary and sufficient condition for Eulerian graph). An undirected graph is
Eulerian iff. it is connected and degrees of all vertices are even.

Proof.

1. Necessarity. The Eulerian graph is connected. Assume the contrary: there exists a
vertex with odd degree. Let’s delete the edges of the current graph one by one through
the Eulerian cycle. Since we go in to the vertex by one edge and go out from this vertex
by another edge, each time after visiting a vertex the degree of this vertex decreased
by 2, and hence the parity of this vertex degree remains the same (note that it also
holds to the starting vertex because of the cycle). Therefore, after the deleting all
edges corresponding to Eulerian cycle (all edges in the graph) the parity of all vertices
remains the same. It holds the contradiction with existence the vertex with odd degree.

2. Sufficiency. Let’s start any walk in our graph G with deleting visiting edges. This walk
ends in our starting vertex (the first and last vertices in the walk have odd degrees every
time and if vertex has odd degree there exists a unvisited edge adjacent to this vertex).
Therefore, when the walk ends, this walk will form a cycle. Let’s denote the set of
edges of this cycle by C1 .
Consider the graph G \ C1 . Do the same procedure and find the set of edges C2 of a
new cycle in G \ C1 and so on. Let’s denote the set of this sets by C = {Ci }. Since
all vertices have even degree, the set C contains every edge of G. Let’s construct the
Eulerian cycle by using a stack S and the set C:

(a) Start from any vertex of C1 . Take away C1 from C and add it to the stack S.
(b) Go through an edge corresponding to this cycle in the top of the stack S. If there
is no edges corresponding to this cycle, delete the cycle from S and do 2b again.
(c) If there exists an edge corresponding to a cycle Ci from C, take away Ci from C,
add it to the stack S and go to 2b.

This algorithm produces Eulerian cycle in the graph G.

Theorem 14 (Eulerian path existence). An Eulerian path exists in the connected graph iff.
there exist at most two vertices with odd degrees.

Proof.

1. Assume that there are no odd vertices, then there exists Eulerian cycle by the theo-
rem 13.

2. Assume that there are only two vertices with odd degrees u and v.

(a) If there exists an edge (u, v) then after deleting this edge the graph will have no
odd vertices and contains Eulerian cycle by the theorem 13. This Eulerian cycle
with the edge (u, v) forms the Eulerian path.
(b) If there are no edges between u and v, add the edge (u, v) to the graph. Therefore,
the graph with (u, v) will have no odd vertices and contains Eulerian cycle by the
theorem 13. This Eulerian cycle without the edge (u, v) forms the Eulerian path.

31
NB! If there are only two vertices with odd degrees in the graph, an Eulerian path will starts
and ends in these two vertices.

Consider basic Eulerian cycle searching algorithms in connected graphs:

1. Fleury’s algorithm.
This algorithm used the algorithm of testing whether the graph will become not connected
after the deleting current edge.
Description:

(a) Walk in the graph with deleting visiting edges which keep the graph connected.
(b) If deleting all adjacent edges provided the graph to be not connected (all edges are
bridges) go through one of these edges and delete. Do 1a again.

NB! By using Tarjan’s
algorithm for detecting bridges the complexity of Fleury’s algo-
2
rithm will be O ∥E∥ .

2. Using list structure.

This algorithm is based on the algorithm introduced in the theorem 13.
Description:

(a) Construct the set C from the theorem 13 and mark all edges of the graph corre-
sponding to cycles Ci .
(b) Add vertices of C1 to the list L and start from the top.
(c) Go to the next vertex in L. If there exist an edge e adjacent to this vertex not in
the list L and corresponded to a cycle Ci , add all vertices of Ci starting with this
edge at the current position of the list L. Do 2c again.

In the end the list will contain Eulerian cycle.

NB! The complexity of this algorithm is O ∥E∥ ∥V∥ .

3. Using two stacks.

This algorithm used two stack structures S1 and S2 .
Description:

(a) Walk in the graph with deleting visiting edges and add consecutive vertices corre-
sponded to these edges to the stack S1 until it is possible.
(b) Transfer the vertex v in top of the stack S1 to the stack S2 . Do 3a again starting
with the new vertex in the top of the stack S1 .

In the end the stack S2 will contain Eulerian cycle.

NB! The complexity of this algorithm is O ∥E∥ ∥V∥ .

10.2 Hamiltonian graph

An example of 2-vertex connected graph is a Hamiltonian graph.

Definition 10.4. Hamiltoinian cycle is a simple cycle that consist of all vertices of a graph.

Definition 10.5. A graph is called Hamiltonian iff. there exists a Hamiltoinian cycle in the
graph.

32
Lemma 14. Planar graph G is Hamiltonian iff. there exist a representation and a simple cycle
C such that the parts of the dual graph D(G) which belong to int(C) and out(C) are trees.

Proof. We will prove this lemma in the subsection 12.1.

In the general case it is not very easy to give necessary and sufficient conditions for Hamil-
toinian graphs, here we introduce the simplest ones:

Lemma 15 (Necessary Hamiltonian condition). A Hamiltonian undirected graph is 2-connected.

Proof. Assume the contrary: there exists a vertex v in a graph G such that G \ v has at least
two connected components. Hence, if there exists Hamiltonian cycle it should starting and
therefore ending in the same component. This holds the contradiction.

NB! In general situation the construction of Hamiltonian cycle is NP-hardness problem. Thus
knowledge of the Hamiltonian cycle in a graph is used in cryptography namely in the zero-
knowledge protocol.

Lemma 16. Graphs of platonic solids are Hamiltonian.

Proof. The proof is in figure 19.

Figure 19: Hamiltonian cycles in planar representations of Platonic solids graphs.

Let’s introduce several sufficient conditions of Hamiltonian graphs:

Theorem 15 (Ore). Let’s ∥V (G)∥ = n, then

deg(u) + deg(v) ≥ n, for all not adjacent u, v ∈ V (G) =⇒ G is Hamiltonian.

Proof. Let’s assume the contrary: there exists not Hamiltonian graph G that is satisfied the
condition. By the adding edges to the graph G one can obtain S a Hamiltonian graph. Let
G′ be the boundary case: G′ is not Hamiltonian graph and G′ (u, v) — Hamiltonian. The
′
condition of this theorem S also holds for the ′graph G , and the edge (u, v) is the edge of
′
Hamiltonian cycle in G (u, v) (otherwise G is Hamiltonian). Let wn be the next vertex

33
 for w by the Hamiltonian cycle (for some orientation of the cycle). Let V ′ ⊂ V (G′ ) be the
set of vertices w ∈ V ′ such that (v, w) is an edge in G′ and U ′ ⊂ V (G′ ) be the set of vertices
w ∈ U ′ such that (u, wn ) is an edge in G′ .

∥U ′ ∥ = deg(u), ∥V ′ ∥ = deg(v),

U ′ ∪ V ′ ⊂ V (G′ ) \ {v} =⇒ ∥U ′ ∪ V ′ ∥ ≤ n − 1,
∥U ′ ∪ V ′ ∥ = ∥U ′ ∥ + ∥V ′ ∥ + ∥U ′ ∩ V ′ ∥,
∥U ′ ∥ + ∥V ′ ∥ = deg(u) + deg(v) ≥ n =⇒ ∥U ′ ∩ V ′ ∥ ≥ 1.
Thus there exists a vertex w such that the edges (v, w) and (u, wn ) are in the graph G. This
holds contradiction, see figure 20.

Figure 20: Hamiltonian cycle in the case ∥U ′ ∩ V ′ ∥ ≥ 1 in the Ore’s theorem 15.

NB! This theorem has been proved for undirected graphs but it can be proved also for directed
case in the same way.

Theorem 16 (Dirac). Let’s ∥V (G)∥ = n, then

n
deg(u) ≥ , ∀u ∈ V (G) =⇒ G is Hamiltonian.
2
Proof. It simply holds from previous theorem.

NB! For directed graph this theorem also the same.

To prove the next Bondy–Chvátal theorem first several definitions and lemmas are required.
Let’s denote the number of vertices of our graph G by n.

Definition 10.6. The sequence of degrees di = deg(vi ) is called ordered sequence of degrees
iff. d1 ≤ d2 ≤ ... ≤ dn for some re-numeration of the vertices.

Definition 10.7. An ordered sequence of degrees di is majorized by an ordered sequence of

degrees d′i iff. di ≤ d′i for i = 1, 2, ..., n

From this point let consider the numeration of G such that the sequence of degrees G is
ordered.

Statement 2 (Majorized sequance). Let a graph G′ be obtained from a graph G by adding one
edge. Then the ordered sequence of degrees G′ majorizes the ordered sequence of degrees G.

34
 Proof. Let’s the added edge be (vi , vj ), i < j. Then new degrees of vertices vi and vj will be
di + 1 and dj + 1. Let’s prove that after changing di to di + 1 one can re-numerate vertices
such that new ordered sequence d′i will majorize previous one.
Let the number p ∈ Z+ is defined as following: di = di+1 = ... = di+p < di+p+1 .
Now let’s produce the re-numeration:

d′k = dk , k = 1, 2, ..., i[
+ p, ...n and d′i+p = di+p + 1.

The proof ends by doing the same procedure for dj .

Lemma 17 (Upper estimation).

dk ≤ k ⇐⇒ ∥v ∈ V (G) : deg(v) ≤ k∥ ≥ k.

Proof. 1. (⇒).

dk ≤ k ⇒ d1 ≤ d2 ≤ ... ≤ dk ≤ k ⇒ ∥v ∈ V (G) : deg(v) ≤ k∥ ≥ k.

2. (⇐).

∥v ∈ V (G) : deg(v) ≤ k∥ = k+p, p ≥ 0 ⇒ d1 ≤ d2 ≤ ... ≤ dk ≤ ... ≤ dk+p ≤ k ⇒ dk ≤ k.

The same poof for

Lemma 18 (Lower estimation).

dn−k ≥ n − k ⇐⇒ ∥v ∈ V (G) : deg(v) ≥ n − k∥ ≥ k + 1.

Proof. 1. (⇒).

dn−k ≥ n−k ⇒ n−k ≤ dn−k ≤ dn−k+1 ... ≤ dn ⇒ ∥v ∈ V (G) : deg(v) ≥ n − k∥ ≥ k +1.

2. (⇐).

∥v ∈ V (G) : deg(v) ≥ n − k∥ ≥ k + p + 1, p ≥ 0 ⇒
⇒ n − k ≤ dn−k−p ≤ dn−k−p+1 ... ≤ dn−k ≤ ... ≤ dn ⇒ dn−k ≥ n − k.

Lemma 19 (Implication and majorized sequence). If the following implication holds for the
sequence of degrees di :
n
dk ≤ k < =⇒ dn−k ≥ n − k,
2
then it also holds for a majorized sequence of degrees d′i .
Proof. 1. If dk ≤ k < d′k then implication holds by the false first argument,
2. If dk ≤ d′k ≤ k then n − k ≤ dn−k ≤ d′n−k by the majorization property.

Theorem 17 (Bondy–Chvátal). If for an ordered sequence of degrees of a connected graph G

the implication holds:
n
dk ≤ k < =⇒ dn−k ≥ n − k,
2
then G is Hamiltonian.

35
 Proof. Assume the contrary: there exists a graph G that satisfies the condition of the the-
orem. Let G′ be the maximal non-Hamiltonian graph by adding the edges to the graph
G. Thus G′ becomes Hamiltonian by adding any edge. Let’s u and v be two not adjacent
vertices such that deg(u) + deg(v) is maximum in G′ and let deg(u) ≤ deg(v) without loss
of generality.
The graph G′ (u, v) is Hamiltonian. Let like in the Ore’s theorem 15 wn be the next
S
vertex for w by the Hamiltonian cycle. Let V ′ ⊂ V (G′ ) be the set of vertices w ∈ V ′ such
that (v, w) is an edge in G′ and U ′ ⊂ V (G′ ) be the set of vertices w ∈ U ′ such that (u, wn )
is an edge in G′ . Then,
∥U ′ ∥ = deg(u), ∥V ′ ∥ = deg(v),
U ′ ∪ V ′ ⊂ V (G′ ) \ {v} =⇒ ∥U ′ ∪ V ′ ∥ ≤ n − 1,
1. If ∥U ′ ∩V ′ ∥ ≥ 1, then it holds the contradiction like in the Ore’s theorem 15 by figure 20.
2. If ∥U ′ ∩ V ′ ∥ = 0. Let’s denote deg(u) by k.
n
2 k = 2 deg(u) ≤ deg(u) + deg(v) = ∥U ′ ∪ V ′ ∥ ≤ n − 1 < n =⇒ k < .
2
Then ∀w ∈ U ′ :
(a) w doesn’t adjacent to v,


(b) deg(w) ≤ deg(u) = k otherwise deg(w) + deg(v) > deg(u) + deg(v) .
Therefore,
upper estimation n cond. of theorem
∥z ∈ V (G) : deg(z) ≤ k∥ ≥ ∥U ′ ∥ = deg(u) = k =⇒ dk ≤ k < =⇒
2
lower estimation
dn−k ≥ n − k =⇒ ∥z ∈ V (G) : deg(z) ≥ n − k∥ ≥ k + 1,
and thus there exists a vertex z not adjacent to u with deg(w) ≥ n − k. For this vertex
deg(z) + deg(u) ≥ n > deg(v) + deg(u). This holds a contradiction.

Theorem 18 (Whitney). Any planar 4-connected graph is Hamiltonian.

Proof. We will prove this theorem later in the subsection 11.3

11 Planarity and κ-connectivity

11.1 Planarity testing algorithms
By using Tarjan’s algorithm we can delete all 1-cut vertices in a graph and consider just 2-
connected components. Therefore, let’s consider in this section a 2-connected graph without
loss of generality.
Definition 11.1. C-component of the graph G corresponded to a simple cycle C is either
edge that doesn’t belong to the cycle C but connected vertices of C or connected component
of the graph G \ C with all attachments from this subgraph to the cycle C.
Definition 11.2. Two C-components are skew iff. they contains simple paths with starting
points x1 , x2 ∈ C and ending points y1 , y2 ∈ C such that these vertices are in the order
x1 , x2 , y1 , y2 corresponded to some orientation of the cycle C.

36
Definition 11.3. Interplacement graph with respect to cycle C is the graph where vertices
correspond to C-components of the cycle C and edges correspond to the skew relationship
between C-components (see figure 21 for example).
NB! Interpacement graph can have isolated vertices.
Here we will consider the bipartitness property for not connected graphs: not connected
graph is said to be bipartite if each connected component of the graph is bipartite (see figure 21).

Figure 21: The simple cycle C, five C-components C1 , C2 , ..., C5 (left) and bipartite interplace-
ment graph corresponded to the cycle C (right).

Consider a basic algorithm for testing planarity property for 2-connected graphs:
1. Auslander-Parter algorithm.
This algorithm tested planarity property of a 2-connected graph G by checking inter-
placement graphs for each cycle C for bipartitness.
Description:
(a) Find any simple cycle C, e.g. by adding an edge to spanning tree.
(b) Find all connected components of the graph G \ C and add to them edges which
doesn’t belong to the cycle C but connected vertices of C. These will be all C-
components.
(c) Construct interplacement graph and check it for bipartitness. If interplacement
graph is not bipartite, then the graph G is not planar.
(d) For each C-component C ′ construct a new cycle in the subgraph G′ = C C ′ by
S
changing the path through C between any two consecutive (corresponding to some
direction on C) attachments of C ′ to the path between them in C ′ (see figure 22)
and go recursively to the step 1b for the graph G′ .
(e) The recursion terminates when the cycle C has just one C-component in G′ and it
is a path.

Figure 22: A simple cycle C (left, red), C-component C1 (left, black and blue) and a path
between consecutive attachments of C1 in C-component C1 (left, blue). New cycle C (right,
red) and new C-components C2 , C3 (right, black) corresponded to the step 1d of Auslander-
Parter algorithm.

37
 Lemma 20. A 2-connected graph is planar iff. for each simple cycle C:
(a) the interplacement graph is bipartite,
(b) for each C-component C ′ the subgraph C C ′ is planar.
S

Proof. If all conditions held then the planar representation can be constructed by re-
verse steps of recursion in Auslander-Parter algorithm.

NB! If a graph is planar (if algorithm doesn’t terminate earlier) the number of vertices
which belong to int(C)
is decreasing after each step of the recursion. Hence the depth
of recursion is O ∥V ∥ . Since the graph is planar, for this graph ∥E∥ ≤ 3∥V ∥ − 6 and
thus, the

number of
C-components (and thus vetrices of the interplacement graph) is
O ∥E∥ = O ∥V ∥ . Therefore,
the complexity of bipartite testing algorithm for the
interplacement

graph is O ∥V ∥2 . Thus, the complexity of Auslander-Parter algorithm
is O ∥V∥3 .

11.2 3-connectivity
Lemma 21. The minimal non-planar subgraph of a non-planar graph is 2-connected.
Proof. Let’s denote this subgraph by G.
1. Let’s prove that G is 1-connected or just connected. Assume the contrary. Then, this
subgraph G has at least two connected components. Since G is minimal and non-planar,
each component should be planar and therefore, subgraph G is also planar. This holds
contradiction.
2. Let’s prove that G is 2-connected. Assume the contrary. Then, there exists a vertex
v, such that by deleting v graph becomes not connected and thus has at least two
connected components. Let’s denote one of the components by G1 and by G2 all theSrest.
Since the subgraph G isSminimal and non-planar, the induced subgraphs on V (G1 ) {v}
vertices and on V (G2 ) {v} vertices are planar. By using corollary 4 representations of
these subgraphs can be modified such that the vertex v would belong to the boundary
of outer faces of these subgraphs. Therefore, the union of representations of these
subgraphs will be planar and it is representation of the whole graph G. This holds
contradiction.

Lemma 22. If the minimal non-planar subgraph of a non-planar graph doesn’t contain subdi-
visions of complete graphs K5 and K3,3 then this subgraph is 3-connected.
Proof. Let’s assume the contrary. Denote the minimal non-planar subgraph by G. By
lemma 21 the subgraph G is 2-connected, then, there exist two vertices u and v, such that
by deleting them G becomes not connected. Let’s denote the connected components of the
G \ {u, v} by H1 , H2 , ..., Hk . S
Let Mi be an induced subgraph on vertices V (Hi ) {u, v}. Let’s prove that each Mi is
also connected. Assume the contrary: Mi is not connected. Thus, Hi = Mi \ {u, v} has
connections to only one vertex. Then, the graph G becomes not connected after deleting this
vertex. This contradicts to the 2-connectivity of G. Therefore, each Mi has connections to
both vertices u and v and thus, connected.
Assume that all Mi + (u, v) (either Mi with the edge (u, v) or just Mi if u and v are
adjacent) are planar, then one can combine them for a whole planar representation by putting

38
 them inside each other (see figure 23). Therefore, ki=1 Mi + (u, v) = G + (u, v) is planar.
S

This contradict with non-planarity of G. Thus, there exists non-planar Mj + (u, v).

Sk

Figure 23: Planar representation of i=1 Mi + (u, v) for lemma 22.

Since G is the minimal non-planar subgraph that contains no subdivisions of graphs K5

and K3,3 , the graph Mj + (u, v) should contain subdivisions of graphs K5 or K3,3 . Since all
S for any k ̸= j there exists path Puv between u and v in Mk and therefore,
Mi are connected,
the graph Mj Puv ⊂ G contains subdivisions of graphs K5 or K3,3 . This holds contradiction
since G doesn’t contain subdivisions of graphs K5 and K3,3 .

Now let’s prove the Pontryagin-Kuratowski theorem:

Theorem 19 (Pontryagin-Kuratowski). A connected graph is planar iff. it doesn’t contain
subdivisions of complete graphs K5 and K3,3 .
Proof. Necessarity holds from lemmas 9 and 10.
Sufficiency. Assume the contrary: there exists non-planar graph that doesn’t contain subdi-
visions of complete graphs K5 and K3,3 . Let’s consider it’s minimal non-planar subgraph G.
By lemma 22 this subgraph G is 3-connected.
Consider two adjacent vertices u and v. Since G is minimal non-planar subgraph, G′ =
G \ (u, v) is planar. By corollary 5 the subgraph G′ is at least 2-connected and by Menger’s
theorem there exist two vertex independent paths from u to v. Thus, there exists a simple
cycle in planar representation of G′ that contains vertices u and v. Let C be the simple cycle
that contains u and v in planar representation of G′ with the maximum edges in int(C).
If there exists a vertex that belongs to the out(C) one can construct the cycle that
contains more edges in inner part than in int(C) (see figure 24). Thus all vertices of the
planar representation G′ belong to int(C).

Figure 24: A cycle (blue) with more edges in inner part than in int(C).

39
 Let’s give some additional definitions which are necessary for the proof: let’s denote by
bridge of cycle C in planar representation of G′ a simple path starting and ending in vertices
of C that doesn’t contain another vertices and edges of C (this “bridge of cycle” definition
is not general definition in graph theory we use this definition only in this theorem. The
general another definition of a bridge will be introduced in section 9.2.). If bridge laying in
out(C) then it is called outer bridge, if it is in int(C) then it is called inner bridge. Since
the subgraph G′ is connected and all vertices except V (C) belong to int(C), all connected
components of G′ \ C are inner C-components.
Now all preparations are done. Let’s prove this theorem step by step:

1. If there is no inner (outer) bridges in G′ then there exists planar representation of G.

This holds a contradiction, thus there exist at least one inner and one outer bridge.

2. If all inner bridges in G′ are not skew with (u, v) then also there exists planar repre-
sentation of G. This holds a contradiction, thus at least one inner bridge is skew with
(u, v). Let’s denote this inner bridge by B1 .

3. Since there is no vertices belongs to out(C), all outer bridges are edges.

4. If there exists an outer bridge in G′ that is not skew with (u, v) one can extend the cycle
C such that it will contain more edges (like in figure 24). This holds a contradiction,
thus all outer bridges are skew with (u, v). Let’s denote an outer bridge by B2 .

5. Any two inner C-components are not skew otherwise they intersect and form one whole
C-component.

6. If a C-component is skew with (u, v) and outer bridge then G contains a subdivision
of K3,3 (see figure 25). This holds a contradiction, thus either C-component skew with
an outer bridge or C-component skew with (u, v).

7. If there doesn’t exist bridges from u to v, then, let’s divide C-components of the graph
G′ by two groups: the first is (u, v) and all inner C-components which are not skew with
(u, v) and the second — outer bridges and inner C-components which are skew with
(u, v). The interplacement graph of these C-components (including the edge (u, v)) is
bipartite by this division and the property 6 and since all C-components are planar (G′
is planar) then G is planar by the lemma 20. This holds a contradiction, thus there
exists a bridge from u to v. Let’s denote it by B3 .

Since the subgraph G′ is planar, the bridge B1 should intersect with B3 in some points.
Consider the cases of relative positions of B1 , B2 and B3 :

1. The bridges B1 and B2 don’t intersect.

2. The bridges B1 and B2 intersect in 1 point.

3. The bridges B1 and B2 intersect at least in 2 points.

And

a. Bridges B1 and B3 intersect in 1 point.

b. Bridges B1 and B3 intersect at least in 2 points.

40
 For cases 1ab, 2ab and 3b the subgraph G contains a subdivision of K3,3 (see figure 25).
For the case 3a it is easy to see that the subgraph G contains a subdivision of K5 . This holds
the contradiction and ends the proof.

Figure 25: The subdivisions of K3,3 in the Pontryagin-Kuratowski theorem for the case 6 (left,
top), for the cases 1ab (right, top), 2ab (left, bottom), 3b (right, bottom) marked as red.

Another result about a connection between planarity and connectiveness is

Theorem (Steinitz). A connected graph is planar and 3-connected iff. it is graph of a convex
polyhedron.

We will prove this theorem in subsection 12.2.

11.3 4-connectivity
First let’s introduce famous Thomassen theorem for C-components

Theorem 20 (Thomassen). Let Cout be a simple cycle corresponded to outer face of 2-connected
planar graph G. Consider a vertex v and an edge e of Cout and any another vertex u. Then
there exists simple cycle C that contains u, v and the edge e such that

1. Each C-component has at most 3 vertices of attachments,

2. Each C-component containing an edge of Cout has at most 2 vertices of attachments.

The proof for this theorem is complicated, thus we just give a reference [5] and simply prove
the theorem about 4-connected graphs

Corollary 7. (Whitney). Any planar 4-connected graph is Hamiltonian.

41
 Proof. Since the outer face should contain at least 3 vertices, let’s choose an edge e ∈ Cout
not adjacent to v ∈ Cout and u ∈ / Cout . The simple cycle C corresponded to Thomassen
theorem 20 should be Hamiltonian cycle (otherwise there exists C-component with ∥V (C)∥ ≥
1 that has at most 3 attachments and it holds a contradiction with 4-connectivity).

12 Duality
12.1 Dual graphs
Definition 12.1. Dual graph D(G) corresponded to a planar representation of a graph G is
the graph constructed as following: in each face Fu of the graph G add corresponded vertex u
for dual graph, if two faces Fu and Fv adjacent to each other, then add the edge (u, v).
The dual graphs are defined only for planar graphs, thus we omit the planar properties in
this subsection for short.

NB! Dual graph can contain loops and multi-edges (see figure 26).
NB! For isomorphic graphs dual graphs can be non-isomorphic (see figure 26 left).
NB! Non-isomorphic graphs can have isomorphic dual graphs (see figure 26 right).

We see that in the case then dual graph is not simple there are many non-trivial non-intuitive
difficult things. In this case 1-cycles (loops) and 2-cycles (multi-edges) can be considered as
simple-cycles and thus consider planar representations for not only simple graphs.

Figure 26: Not isomorphic dual graphs for two different planar representations of one simple
graph (left). Isomorphic dual graphs for non-isomorphic simple graphs (right).

Lemma 23. Dual graph is connected.

Proof. For any two vertices in dual graph D(G) there exists a curve started from the first
point and ended in the second point that doesn’t contain vertices of G. The sequence of faces
and edges traversed by this curve corresponds to the path between these two points in D(G).

42
Lemma 24. Dual graph is planar.

Proof. Any edge (u, v) of a dual graph corresponds to the adjacency property of two T faces
Fu and Fv and thus can be matched with the edge of the graph G that belongs to Fu Fv .
S representation of the dual graph such that u ∈ int(Fu ) and
Therefore, one can redraw this
v ∈Sint(Fv ) and (u, v) ⊂ Fu Fv and moreover, there exists small neighborhood U (u, v) ⊂
Fu Fv .
Assume the contrary, that dual graph is not planar. Then, for any representations of the
dual graph there exist two edges e1 and
S e2 which intersect. Hence
S there exists neighborhood
of e1 and e2 such that U (e1 ) ⊂ Fu1 TFv1 and U (e2 ) ⊂ Fu2 Fv2 respectively.
S T Thus,S there
exists common open set W = U (e1 ) U (e2 ) such that W ⊂ (Fu1 Fv1 ) (Fu2 Fv2 ). It
holds contradiction since faces of a planar representation can intersect only by edges but not
by open sets.

Lemma 25. Planar graph G is Hamiltonian iff. there exist a representation and a simple cycle
C such that the parts of the dual graph D(G) without the vertex corresponded to the outer face
which belong to int(C) and out(C) are trees.

Proof. The existence of vertex of the graph G that belongs to int(C) or out(C) is equivalent
to the existence of a cycle in the dual graph D(G).

Lemma 26. Let’s G be connected graph. Dual graph D(G) is simple iff. G is 3-edge connected.

Proof. A loop in the dual graph D(G) corresponds to a bridge in the graph G. Therefore,
the absence of loops corresponded to 2-edge connectivity of the graph G. Multi-edges in
D(G) correspond to adjacent faces, which have several common adjacent edges. Thus, the
additional absence of multi-edges is corresponded to 3-edge connectivity of the graph G.

Corollary 8. Let’s G be connected graph. Dual graph D(G) has no loops iff. G is 2-edge
connected (or equivalently G has no bridges).

Lemma 27 (Squared duality). For 2-edge connected graph G with no loops holds

D(D(G)) = G.

Proof. First, let’s provide the matching between vertices of the graph G and faces of dual
graph D(G). Consider a vertex u of the graph G. Denote adjacent edges by (u, ui ) for i =
1, 2, ..., k and the faces which contain (u, ui ), (u, ui+1 ) for i = 1, 2, ..., k − 1 and (u, uk ), (u, u1 )
by F1 , F2 , ..., Fk sequentially. These faces correspond to vertices v1 , v2 , ..., vk of the dual graph
respectively. Since the graph is 2-edge connected with no loops, dual graph D(G) also has
no loops. Therefore, Fi ̸= Fi+1 for i = 1, 2, ..., k − 1 and Fk ̸= F1 . Thus, each pair Fi , Fi+1
and Fk , F1 intersect for i = 1, 2, ..., k − 1 by the edge (u, ui+1 ) and (u, u1 ) respectively and
thus there is matching between edges (u, ui+1 ) and (vi , vi+1 ) and (u, u1 ) and (vk , v1 ). This
matching continues to a matching of the vertex u and a simple cycle v1 v2 ...vk in the dual
graph (see figure 27). Thus, we matched every vertex with a simple cycle (or face).

43
Figure 27: Matching between multi-angle and simple cycle for the graph G and the dual graph
D(G) in lemma 27.

Now let’s consider a vertex v of the dual graph D(G). This vertex corresponds to some
face Fv of the graph G. The boundary of the face Fv is a simple cycle (since there are no loops
in G). Let’s denote this cycle by u1 u2 ...uk . For each vertex ui of the graph G there exists a
matching face Fi of the dual graph such that these faces adjacent sequentially to each other
due to the
T matching property of edges of D(G) and G (each edge (ui , ui+1 ) corresponded to
edge Fi Fi+1 ). Since all faces Fi have sequentially intersections in int(Fv ) and there are no
another edges which belong to int(Fv ), the intersection ki=1 Fi = v (see figure 28).
T

Figure 28: Matching between multi-angle and simple cycle for graph D(G) (blue) and graph G
(black) in lemma 27.

Therefore, any multi-angle of the graph G (the set of faces which contain correspondent
vertex) matches
bijectively with a face of the graph D(G) and vice versa.

Thus, for every
vertex D D(v) = v and for every edge e adjacent
to this vertex D D(e) = e. This can be
continued for a whole graph and thus, D D(G) = G.

Corollary 9. For 2-edge connected graph G with no loops holds

∥V D(G) ∥ = ∥F (G)∥, ∥E D(G) ∥ = ∥E(G)∥, ∥F D(G) ∥ = ∥V (G)∥.



Proof. By definition: ∥V D(G) ∥ = ∥F (G)∥.
By lemma 24: ∥E D(G) ∥ = ∥E(G)∥. Using
the correspondence in lemma 27: ∥F D(G) ∥ = ∥V (G)∥.

NB! These lemma and corollary also hold for any connected graphs but the proof is more
complex because of loops.
Corollary 10. Any non-isomorphic 2-edge connected planar graphs with no loops have non-
isomorphic dual graphs.

44
 Proof. It holds from the bijection in lemma 27.

NB! If dual graph has loops this corollary doesn’t hold. The example can be constructed as in
figure 26 right-bottom, if split the connected vertex to an edge between two triangles and then
move the obtained loop of the dual graph such that a leaf will appear in the dual of dual graph.

Lemma 28. Dual graph D(G) has no loops, 2-connected and planar iff. graph G has no loops,
2-connected and planar.

Proof. Let’s prove sufficient condition. The necessary condition will hold by the lemma 27.
Assume the contrary: the dual graph D(G) has a vertex v such that it becomes not
connected after deleting u. Consider two connected components
S G1 and S G2 in D(G). Let’s
M1 and M2 be induced subgraphs on vertices V (G1 ) {v} and V (G2 ) {v} respectively.
These subgraphs M1 and M2 should contain cycles f1 and f2 respectively, otherwise one of
them is a
tree and it holds a contradiction using the lemma 27. Let’s denote the vertices of
D D(G) = G corresponded to faces f1 and f2 by u1 ∈ G and u2 ∈ G (see figure 29). Let’s
denote the vertex corresponded to outer face of D(G) by u. Since any inner faces of M1 have
no adjacent edges with any inner face of M2 , any path from vertex u1 to u2 should contain
u. This holds a contradiction with 2-connectivity of G.

Lemma 29. Dual graph D(G) is simple, 3-connected and planar iff. graph G is simple 3-
connected and planar.

Proof. The proof for this theorem is the same as for the previous lemma, but in this case
one should consider two faces: outer face that corresponds to the vertex u ∈ G and “middle”
face f that corresponds to the vertex w ∈ G (see figure 29).

Figure 29: Graph G and dual graph D(G) for lemmas 28 (left) and 29 (right).

12.2 Steinitz theorem

Let’s start with several definitions and lemmas:

Definition 12.2. Contraction of an edge (u, v) is the operation that transform the graph
′ ′ ′

S graph G by merging vertices u and v to a new vertex w ∈ V (G ): V (G ) = V (G) \
G to the
{u, v} {w} (see figure 30).

Definition 12.3. Minor of a graph G is a graph that is obtained from G by contraction and
deleting operations of edges.

45
Definition 12.4. In series reduction is a contraction of an edge adjacent to the vertex of degree
two. In parallel reduction is deleting multiple edges between to vertices. SP-reduction of
graph is a sequence of series and parallel reductions obtained for this graph (see figure 30).

Figure 30: Deleting (left-top) and contraction (right-top) operations. In series (left-bottom)
and in parallel (right-bottom) reductions.

Definition 12.5. Grid graph G(k, l) is the graph on the plane with vertices coordinates
{(a, b) : 0 ≤ a ≤ k − 1, 0 ≤ b ≤ l − 1} such that two vertices are connected if either their
x-coordinates differ by 1 and y coincide or y-coordinates differ by 1 and x coincide.

Lemma 30. Any planar graph is a minor of a grid graph.

Proof. Consider some representation of a planar graph G on the plane R2 . We can split any
vertex such that G will have a vertices of maximum degree 4 (see figure 31). Let’s Ur (v)
be a diskSin R2 with center in v and radius r, ∂Ur (v) be the boundary of the disk and
Ur (e) = Ur (p), where p ∈ R2 are points of an edge e.
p∈e

Figure 31: Splitting in small neighbourhood of vertex with degree more than 4 to vertices which
has maximum degree 4 for lemma 30.

Let’s find ϵ1 , ϵ2 and ϵ3 such that:

1. Consider for every vertex vj a point vj′ ∈ Uϵ3 (vj ) with rational coordinates. For any j:
Uϵ3 (vj ) ⊂ Uϵ1 (vj′ ).

2. For any j the number of intersections of ∂Uϵ1 (vj′ ) and an edge e should be equal to 1
for e adjacent to vj and 0 otherwise.
Sn 
3. For any edge e all regions Uϵ2 (e)\ Uϵ1 (vj′ ) are connected and disjoint.
j=1

Since Uϵ3 (vj ) ⊂ Uϵ1 (vj′ ), the vertex vj ∈ Uϵ1 (vj′ ). Let’s denote by ei,j the intersections
of edges ei and ∂Uϵ1 (vj′ ). Consider the points with rational coordinates pi,j ∈ ∂Uϵ1 (vj′ ) such
that pi,j ∈ Uϵ2 (ei,j ). Since all vertices have the maximum degree 4, any ∂Uϵ1 (vj′ ) can contain
maximum 4 different points pi,j .

46
 Let’s scale the coordinates of R2 by multiplication for the product of denominators of all
corresponding points. Thus all corresponded points will have integer coordinates. For any
region corresponded to Uϵ1 (vj′ ) there exists the natural number Cj for scaling coordinates of
R2 such that after scaling there exist less or equal four vertex independent paths from vj′ to
pi,j ∈ ∂Uϵ1 (vj′ ) with consequent vertices in Uϵ1 (vj′ ) with either their x-coordinates differ by 1
and y coincide or y-coordinates differ by 1 and x coincide. There exist natural numbers Di
Sn 
′
with the same properties for any region Uϵ2 (ei ) \ Uϵ1 (vj ) and two vertices pi,j and pi,k
j=1
corresponded to the edge ei . By scaling, finally for the product of all Cj and Di and shifting
coordinates one can obtain required grid graph.

Definition 12.6. ∆Y operation is an operation replacing a triangle that bounds a face by

3-star that connects the same vertices or vice versa (see figure 32). If a triangle transforms to
3-star it is called ∆-to-Y operation and the reverse is called Y -to-∆ operation.

Figure 32: ∆Y operation.

Because ∆Y operations can cause multi-edges in a new graph, thus in this subsection all
graphs can be considered as not simple by default.

Lemma 31. Let v ∈ G is a vertex of degree 3 that has three non-parallel adjacent edges
(e, f, g).

1. If G has no loops, planar and 2-connected, then the result of Y -to-∆ operation to (e, f, g)
and then series of SP -reductions also has no loops, planar and 2-connected.

2. Let G be simple, planar, 3-connected graph and not K4 , then the result of Y -to-∆ operation
to (e, f, g) and then series of SP -reductions is also simple, planar, 3-connected.

Proof. By Mengers theorem 26 there exist 2 or 3 vertex independent paths between any two
vertices in G. Paths which don’t contain vertex v after Y -to-∆ operation will not change.
There can be only one path from these independent sets that contains vertex v and thus
edges e and f without loss of generality. After Y -to-∆ operation this path will walk through
the new edge g.

Lemma 32. Let (e, f, g) be three non-parallel edges which form a triangle.

1. If G has no loops, planar and 2-connected, then the result of ∆-to-Y operation to (e, f, g)
and then series of SP -reductions is also has no loops, planar and 2-connected.

47
 2. Let G be simple, planar 3-connected graph, then the result of ∆-to-Y operation to (e, f, g)
and then series of SP -reductions is also simple, planar and 3-connected.

Proof. Let’s note that Y -to-∆ operation for a graph G corresponds to ∆-to-Y for the dual
graph D(G) and vice versa. Also in series reduction for the graph G corresponds to in parallel
reduction for the dual graph D(G) and vice versa. The multi-edges correspond to the object
in dual graph that can be reduced by in series reduction to just one edge. By using this facts
and lemmas 28 and 29 this lemma is led to the previous one.

Definition 12.7. A 2-connected graph G is ∆Y reducible to the graph G′ if it can be

transformed to the graph G′ by sequence of ∆Y operations and SP -reductions.

Lemma 33. Any grid graph G(k, l) : k, l ≥ 3 is ∆Y reducible to the graph K4 .

Proof. Let’s use two following operations (figure 33) in the grid graph G(k, l).

Figure 33: Two operations in lemma 33: operation 1 for triangle with adjacent vertex with
degree 3 (top) and operation 2 for triangle with adjacent vertex with degree 4 (bottom).

First, let’s use in series reduction to transform the left-bottom and right-top squares to
triangles. Then, transfer the left-bottom triangle to the top row by series of operation 2. If
by this the multi-edges are obtained, use in parallel reduction, if it is not, use operation 1 to
delete transferred triangle. Use this procedure for second square in the bottom row. By this
procedure one can delete all squares of the bottom row. The symmetrical procedure can be
used for deleting columns from left to right. Therefore, this grid graph can be reduced to the
grid graph G(2, 2). See figure 34 to obtain the graph K4 from G(2, 2).

Figure 34: The series of reductions to obtain the graph K4 from G(2, 2) for lemma 33.

48
 Let’s C2 be a circle with two vertices and two multi-edges between them.

Lemma 34. If a planar graph with no loops G is ∆Y reducible to the graph C2 , then so is for
every 2-connected minor without loops of G.

Proof. Let’s prove it by induction for the number of ∆Y reductions necessary to obtain the
graph C2 :
The base: any 2-connected minor of C2 is C2 .
Now, let for every G that can be ∆Y reduced to the graph C2 by k steps, every 2-
connected minor is also ∆Y reducible to C2 . Let’s prove it for G that can be ∆Y reduced to
the graph C2 by k + 1 steps. Consider the graph G′ after one step of ∆Y reduction. Let’s H
be a 2-connected minor without loops of G.

1. If H doesn’t contain the part that is changed by current ∆Y reduction from G to G′

then H is 2-connected minor of G′ . Therefore, H is ∆Y reducible to C2 by the inductive
assumption.

2. If H contains whole part that is changed by current ∆Y reduction from G to G′ , then

this reduction can be used in H to obtain the graph H ′ . By the lemmas 31 and 32
H ′ will be 2-connected minor without loops of G′ . Therefore, H ′ and hence H are ∆Y
reducible to C2 .

3. If H doesn’t contain whole part, then the current reduction is ∆-to-Y or Y -to-∆. Let’s
denote the corresponding edges by (e, f, g), and e or e, f will be the part of the graph
H without loss of generality. Let’s consider cases:

(a) The current reduction is ∆-to-Y .

i. If H can be obtained from G by one contraction of the edge g then H will be
the minor of G′ by contraction of corresponded edges e, f in G′ .
ii. If H can be obtained from G by contraction of two edges or more, then H
will contain a loop. This holds a contradiction.
iii. If H can be obtained from G by one deletion of the edge g then H will be the
minor of G′ by contraction the corresponded edge g in G′ .
iv. If H can be obtained from G by deletion of the edges f, g then H will be the
minor of G′ by the deletion of the corresponded edge e and contraction the
corresponded edge f or g in G′ .
(b) The current reduction is Y -to-∆.
i. If H can be obtained from G by contraction of any edges then H will contain
a loop. This holds a contradiction.
ii. If H can be obtained from G by deletion of one edge g then let’s H ′ be the
graph that is obtained by H by in series reduction of the part {e, f }. Since
H ′ is a minor of G′ , the minor H ′ and hence H are ∆Y reducible to C2 .
iii. If H can be obtained from G by deletion of two or more edges then H will be
not 2-connected. This holds a contradiction.

This ends the proof.

Corollary 11. Any simple 3-connected planar graph G is ∆Y reducible to the graph K4 .

49
 Proof. By the lemma 30 G is a minor of a grid graph G(k, l). This grid graph G(k, l) is ∆Y
reducible to the graph K4 by the lemma 33. Let’s note that K4 is also ∆Y reducible to C2 .
Hence, G is ∆Y reducible to C2 by the lemma 34.
Let’s prove that G is ∆Y reducible to K4 by the induction of the number edges in G:

1. The base. A simple 3-connected planar graph with the smallest number of edges is K4
by the lemma 11 for (k, l, d) graphs.

2. Let’s any simple 3-connected planar graph with k edges is ∆Y reducible to K4 . Let’s
prove it for G with k + 1 edges. Consider the ∆Y reduction of G to C2 . Since C2 has
only two edges, there will be step with SP -reduction in ∆Y sequence. Let’s G′ be the
graph that is obtained from G after the first SP -reduction. By the lemma 29 G′ is
simple, planar, 3-connected and has less edges than G. Then G′ and hence G are ∆Y
reducible to K4 by the inductive assumption.

Theorem 21 (Steinitz). Let’s G be simple connected graph. Then, G is planar and 3-connected
iff. it is graph of a convex polyhedron.

Proof.

1. Necessarity. Let’s prove the following: let G′ be a graph that obtained from G by one
∆Y operation and SP -reduction and G′ be a graph of a convex polyhedron P (G′ ) then
G is also a graph of a convex polyhedron P (G). Let’s consider cases:

(a) If the current ∆Y operation is ∆-to-Y operation then the polyhedron P (G) can be
obtained from the polyhedron P (G′ ) by the section of the plane π (see figure 35).

Figure 35: ∆-to-Y operation without SP -reduction (left-top) and corresponded section of the
polyhedron P (G′ ) by the plane π (left-bottom). ∆-to-Y operation with SP -reduction (in series,
right-top) and the corresponded section of the polyhedron P (G′ ) by the plane π (right-bottom).

(b) If the current ∆Y operation is Y -to-∆ operation. Consider the corresponded

triangle T ∈ P (G′ ). This triangle is adjacent to three faces F1 , F2 , F3 . If faces
F1 , F2 and F3 intersect in one point then the polyhedron P (G′ ) is tetrahedron,
G′ is K4 and polyhedron P (G) can be constructed by gluing two tetrahedrons to
each other. Thus P (G) is convex and corresponds to the graph G.

50
 Now let’s faces F1 , F2 and F3 don’t intersect in one point. Then, do the reverse
operation like in figure 35 left, but with some deformation: compress the triangle
in the face T and deform P (G′ ) such that planes corresponded to F1 , F2 and F3
become intersected in one point (see figure 36) and extend current faces to this
intersection. Obtained polyhedron will be convex and correspond to the graph G.

Figure 36: Deformation of the polyhedron P (G′ ) corresponded to the case 1b of the Steinitz
theorem.

Let’s note that in each case all transformations been done preserve convexity of the
polyhedron.

2. Sufficiency. In the Euler theorem 10 the planarity property was proved. Let’s prove
that by deletion of any two vertices u, v the graph G remains connected.

(a) Consider the case when u, v are vertices of the common face π. Let’s prove that
for any two vertices ∈
/ π there exists path between them that doesn’t intersect the
face π. Consider the path P between any two vertices in G. Let’s transform this
path by following:
i. Consider the case when P contains an edge e ∈ π. Let’s denote S the another
adjacent face (not π) by F . Transform the path P to (P \ e) (F \ e). Since
faces F and π can intersects only by one edge (property 2 of polyhedrons),
the number of edges in the T path P which belongs to π will decreased by 1.
Do this for every edge in P π.
ii. If P contains a vertex v ∈ π. Consider the multi-angle of the polyhedron
corresponded to vertex v (or all faces which contain v). Let’s denote the
adjacent to v edges in P by e1 and en . For the edge e1 there exists a face
F1 ̸= π that contains e1 . Let’s do the transformation like in case 2(a)i for the
edge e1 . By this transformation the edge e1 transforms to the path through
the face F1 . Let’s denote the new edge of F1 adjacent to the vertex v by e2
and continue this procedure

S for e2 and so
on. In the end transform the path
P to P \ {en−1 , en } Fn−1 \ {en−1 , en } .
By this transformations one can modify the path between any two vertices ∈ / π
by a path that doesn’t intersect the face π. Therefore, there exists path between
any two vertices in G \ {u, v}.
(b) Let’s vertices u, v don’t belong to the same face. Consider the path between any
two vertices that contains the vertex u without loss of generality. Transform the
path using procedure in the case 2(a)ii. Since vertices u, v don’t belong to the
same face, the faces F1 , F2 , ..., Fn−1 don’t contain the vertex v and hence, the new

51
 transformed path doesn’t contain the vertices u and v. Therefore, there exists a
path between any two vertices that doesn’t contain the vertices u and v.

12.3 Dual polyhedrons

Definition 12.8. Dual polyhedron D(P ) for a convex polyhedron P is defined by following:
1. Consider the 3-dimensional coordinates of vertices of polyhedron P . Each face v1 v2 ...vk ∈
P match with the vertex u = k1 ki=1 vi .
P

2. If any two faces of P are adjacent then add an edge in the dual graph D(P ) between two
vertices which are matched to these faces.
NB! A dual polyhedron is unique by this construction.
NB! The graph of dual polyhedron D(P ) is dual to the graph of a polyhedron P .


Lemma 35. int D(P ) ⊂ int(P ).
Proof. By using convex property:



∀u, v ∈ V D(P ) ⇒ u, v ∈ ∂P ⇒ (u, v) ⊂ int(P ) ⇒ D(P ) ⊂ P ⇒ int D(P ) ⊂ int(P ).

Lemma 36. The dual polyhedron is convex.

Proof. Since the graph of dual polyhedron D(P ) is dual to the graph of a polyhedron P , this
matching can be continued in the same way like in the lemma 27 to the matching between
faces and multi-angles of the polyhedron P and the dual polyhedron D(P ) such that edges
of faces are corresponded to edges of multi-angles, and vertices of faces are corresponded to
faces of the multi-angles (see figure 37).
Now let’s assume the contrary:

there exist two faces F1 , F2 ∈ D(P ) such that the edge
(u, v) : u ∈ F1 , v ∈ int D(P ) intersect the face F2 . The vertex v ∈ int(P ) by lemma 35. By
the correspondence below there are a multi-angles at vertices h1 and h2 which match to the
faces F1 and F2 (see figure 37 left). Hence, this edge (u, v) intersects with the polyhedron P
and u ∈ P and v ∈ int(P ). This holds a contradiction.

Figure 37: For the lemma 36: correspondence between a face of dual polyhedron D(P ) (blue,
left) and a multi-angel of polyhedron P (black, left). Two faces F1 and F2 , the edge (u, v) of
dual polyhedron D(P ) (blue, right) and corresponded multi-angels at vertices h1 and h2 .

52
 Consider the duality relationship for platonic solids (see figure 38):

1. Tetrahedron → Tetrahedron,

2. Octahedron → Cube,

3. Icosahedron → Dodecahedron,

4. Cube → Octahedron,

5. Dodecahedron → Icosahedron.

Figure 38: Dual polyhedrons for platonic solids.

Theorem 22 (Whitney). Any planar 3-connected graph has unique dual graph up to isomor-
phism.

Proof. Let’s assume the contrary: a planar 3-connected graph G has two non-isomorphic
dual graphs D1 and D2 . By the Steinitz theorem 21 any 3-connected graph G is a graph of a
convex polyhedron P (G). Any dual graph
D(G) is 3-connected by the lemma 29 thus it is also
a graph of a convex polyhedron P D(G) . Since D1 and D2 are not isomorphic, the graphs
of two polyhedrons P (D
1 ) and P (D2 )
are not isomorphic. By the lemma 27 graphs of dual
polyhedrons D P (D1 ) and D P (D2 ) are isomorphic

to the
graph G and thus isomorphic.
Let’s denote this isomorphism by i1 : D(P D1 ) → D P (D2 ) . By matching in the lemma

27
′ 2

2
this isomorphism defines isomorphism

of their duals: i1 : D P (D
1 ) → D P (D2 ) , and
dual polyhedron D P (D1 ) is isomorphic to P (D1
) and D2 P (D2 ) is isomorphic
2

to P (D2 ).
Let’s denote these isomorphisms by i2 : D2 P (D1 ) → P (D1 ) and i3 : D2 P (D2 ) → P (D2 ).
The composition i3 ◦ i′1 ◦ i−1
2 is isomorphism P (D1 ) → P (D2 ).

12.4 Algorithms
Dual graph constructing algorithm.

53
 This algorithm constructed the dual graph D(G) corresponding to a planar representation
of a connected graph G.

Description:
 
1. Initialize 2-dimensional array a = a1 [v], a2 [v] corresponded to edges of a dual graph
D(G) with dimensions 2 × ∥E(G)∥.

2. Find all bridges using bridge-detecting algorithm.

3. e ∈ G and use any algorithm of searching shortest path

S P in G \ e between two vertices
adjacent to the edge e to find a simple cycle C = P1 e in G.

4. Check that this cycle is new cycle by checking whether all a[j] corresponded to the edges
of C don’t contain the same vertex. If it is not new cycle find another shortest S
path P2
(by deleting one of adjacent edges to e in P1 ) in G \ e again and change C = P2 e.

5. For every edge ej ∈ C add new vertex v either in a1 [j] or in a2 [j] if a1 [j] is not empty.

6. Do 3-5 for every another edge in G.

7. For each empty a2 [j] add a vertex v0 that corresponds to the outer face of the graph.

8. For every not assigned bridge b find the path P from this bridge
S to a vertex that contains
an edge ei with not empty a2 [i]. For every bridge ej ∈ P b add in a1 [j] and a2 [j] the
value a2 [i].

NB! The complexity of this algorithm

using breadth first search or depth first search for con-
2
nected graphs equals to O ∥E∥ .

Definition 12.9. The dual graph D(G) is called simple* iff. it is simple after the deletion of
vertex corresponded to the outer face of G.

Consider the algorithm corresponded to simple* dual graphs:

Lee algorithm.
This algorithm finds the shortest path through inner faces between any two inner faces of
a planar representation of a graph with simple* dual graph.

Description:

1. Construct the dual graph D(G) for the current graph G and delete the vertex corre-
sponded to outer face of the current graph G.

2. Mark the vertices corresponded to the same depth by this depth (or distance from starting
point) using breadth first search algorithm.

3. Algorithm terminates when the end point is marked.

To find the shortest path walk through the vertices corresponded to reverse order of marked
numbers (from ending point to starting, see figure 39).

NB! The complexity of this algorithm (without constructing
dual graph) equals to the com-
plexity of breadth first search for connected graphs O ∥E∥ .

54
 Figure 39: Result of the Lee algorithm.

Modifications of Lee algorithm:

1. In this algorithm any constructing shortest path algorithm can be used. The complexity
will be equal to the complexity of corresponded algorithm.

2. One can consider different time travelling (and also infinite time travelling) from one face
to another in the planar representation. Thus, the additional weights can be added in
the dual graph. And in this case the shortest path algorithms for weighted graphs can be
used.

3. The breadth first search algorithm can be applied to the starting point and the ending
point in parallel. In this case the shortest path can be constructed when these two
algorithms intersect by a vertex.

4. If one has some information about the dual graph or path (for example, it is known that
the path should contain some vertex). Lee algorithm can be used from this vertex or done
in parallel for the starting vertex, the ending vertex and the current vertex like in 3.

13 Flows on graphs
13.1 Decomposition of flows
Definition 13.1. A flow network is directed graph G with positive weights w(u, v) with two
highlighted vertices s (source) and t (terminal) and capacity function c : V (G) × V (G) →
R+ defined by following: (
w(u, v) (u, v) ∈ E(G)
c(u, v) = .
0 otherwise

Let’s consider a flow network G.

Definition 13.2. A flow is a function f : V (G) × V (G) → R satisfied the following properties:

1. f (u, v) = −f (v, u) (skew symmetry),

2. f (u, v) ≤ c(u, v) (capacity constraint),

P
3. ∀u ∈ V (G) \ {s, t} : f (u, v) = 0 (conservation of a flow).
v∈V (G)

55
 P
A flow f value is F = f (s, v).
v∈V (G)

NB! By skew symmetry a value F of the flow f can be less than 0.

Statement 3 (Sum of flows). Consider a flow network G with two flows: f1 and f2 . If
f1 (u, v) + f2 (u, v) ≤ c(u, v) for any edge (u, v) then f1 + f2 also a flow and F (f1 + f2 ) = F1 + F2 .
Proof. It easy holds from definition.

Theorem 23 (Decomposition of flow). For a positive flow f : F > 0 there exist at most ∥E∥
simple paths Pi from s to t and simple cycles Ci such that
X X X
f= fPi + fCi and F = f (Pi ),
i i i

where f (P ) = min f (e) and

e∈P, f (e)>0

f (P )
 (u, v) ∈ P,
fP (u, v) = −f (P ) (v, u) ∈ P,

0 otherwise.


Proof. Since the flow f is positive, there exists an edge (s, v1 ) with positive flow f (s, v1 ). By
the skew symmetry f (v1 , s) = −f (s, v1 ) and thus by conservation of a flow there exists an
edge (v1 , v2 ) with positive flow f (v1 , v2 ). Then the same holds for the edge (v1 , v2 ). If these
procedure reaches t then denote this path by P1 . If these procedure reaches some visited
vertex then denote the corresponded visited simple cycle by C1 . Let’s denote this cycle or
path just by P . 
f (P )
 (u, v) ∈ P,
′
Consider a flow f (u, v) = −f (P ) (v, u) ∈ P,

0 otherwise.

By decreasing our flow f by this flow f ′ new flow becomes 0 at at least one edge. Then
all edges from the source s will be with 0 flow. This procedure can be obtained for all the
rest vertices with positive adjacent edges. Thus by doing it at most ∥E∥ times we obtain the
decomposition.

This theorem simple implies the decomposition algorithm.

NB! Since the number of steps for constructing a cycle or a path in the theorem 23 less or

equal the number of vertices in the graph and the number
of such cycles and paths is O ∥E∥ ,
the complexity of decomposition algorithm is O ∥V∥∥E∥ .


Definition 13.3. A residual network Gf = V (G), Ef is a flow network with edges Ef with
non-negative residual capacity cf (u, v) = c(u, v) − f (u, v).
Lemma 37 (Two flows). Let f and h be two flows in a flow network G then h can be represented
as a sum f + f ′ , where f ′ is a flow in the residual network Gf with the value F ′ = H − F .
Proof. It easy holds from definition.

Lemma 38 (Subtraction
P of flows). Let f and g be flows with equal values in a flow network
G. Then g = f + fCi , where fCi are flows in the residual network Gf among cycles Ci .
i

56
 Proof. By the previous lemma there exists a flow f ′ in Gf such that g = f + f ′ . Since
F ′ = G − F = 0, the decomposition algorithm will obtain only cycles Ci in the residual
network Gf .

Definition 13.4. A s, t-cut (A, B) is a distribution of the vertex set V (G) by two parts A, B
such that:
S
1. A B = V (G),
T
2. A B = Ø,

3. s ∈ A, t ∈ B.

Definition 13.5. A capacity of the s, t-cut (A, B) is

XX
C(A, B) = c(u, v).
u∈A v∈B

Definition 13.6. A flow through the s, t-cut (A, B) is

XX
F (A, B) = f (u, v).
u∈A v∈B

Lemma 39 (s, t-cut flow). A flow through any s, t-cut is equal to the flow value.
P P
Proof. By the skew symmetry: f (u, v) = 0.
u∈A v∈A
XX XX XX X X
f (u, v) = f (u, v) + f (u, v) = f (u, v) =
u∈A v∈B u∈A v∈B u∈A v∈A u∈A v∈V (G)

conservation low
X X X
= f (s, v) + f (u, v) = F.
v∈V (G) u∈A\{s} v∈V (G)

Corollary 12. The sum of flows from the source is equal to the sum of flows to the terminal.

13.2 Max-flow
Definition 13.7. Max-flow is a flow with the maximum possible value in a flow network.

NB! The value of the max-flow should be non-negative.

Lemma 40 (Necessary and sufficient condition of positive max-flow value). The max-flow value
is positive iff. there exists a path from the source to the terminal.

Proof. 1. Sufficiency. Let cP be the minimum capacity value among the path P . Let’s
define a flow: 
c P
 (u, v) ∈ P,
f (u, v) = −cP (v, u) ∈ P,

0 otherwise.


The flow value is F = cP > 0 thus the max-flow value is positive.

57
 2. Necessarity. Let’s assume the contrary: there is no path from the source to the terminal.
Let’s denote by A a set of vertices which are reachable from the source and B will be
all the rest. Thus c(A, B) = 0 and by s, t-cut flow lemma 39:

0 < F = F (A, B) ≤ c(A, B) = 0

holds contradiction.

NB! For the max-flow a flow value is positive is equivalent to flow value is not zero.
Lemma 41 (About a path in residual network). A flow f is max-flow iff. there is no path
from the source to the terminal in the residual network Gf .
Proof. 1. Necessarity. Let f be the max-flow. Assume the contrary: there exists a path
P from the source to the terminal in the residual network Gf . Let cf,P be the minimum
capacity value in Gf among the path P . Let’s define a flow:

cf,P
 (u, v) ∈ P,
′
f (u, v) = −cf,P (v, u) ∈ P,

0 otherwise.


The flow value F ′ = cf,P . Since f (u, v) + f ′ (u, v) ≤ f (u, v) + cf = c(u, v) the sum f + f ′
is a flow and F + F ′ > F . This holds a contradiction with max-flow assumption.

2. Sufficiency. Assume the contrary: there exists max-flow f ′ ̸= f . By the two flows
lemma 37 the flow f ′ −f is a flow in residual network Gf with the flow value F ′ −F > 0.
Thus the maximal flow on Gf is positive and by the lemma 40 there exists a path in
(Gf )f ′ −f = Gf ′ . This holds the contradiction by necessarity condition.

Definition 13.8. Min-cut is a s, t-cut (A, B) with the minimum capacity (A, B).
Theorem 24 (Ford–Fulkerson). The max-flow value equals to the min-cut capacity value.
Proof. Let f be the max-flow and (Amin , Bmin ) be the min-cut. By the s, t-cut lemma 39:
F = F (Amin , Bmin ) ≤ c(Amin , Bmin ).
By the lemma about a path in residual network 41 there is no paths between the source
s and the terminal t in the residual network Gf . Let’s denote by A the subset of vertices of
Gf which are reachable from s and by B all the rest.

0 = cf (A, B) = c(A, B) − f (A, B) =⇒ F = f (A, B) = c(A, B) ≥ c(Amin , Bmin ) =⇒

=⇒ F = c(Amin , Bmin ).

Consider algorithms for constructing max-flow:

1. Ford–Fulkerson algorithm.
This algorithm finds max-flow in a flow network G from the source s to the terminal t.
Description:

(a) Initialize max-flow fmax = 0.

(b) Find any path P from s to t in G.
(c) Find the minimum capacity cp among this path P .

58
 (d) Construct the flow f with cp among the path as in the lemma 40.
(e) Add new flow f to the max-flow fmax . Do steps 1b- 1d for residual network Gfmax
and find a new flow f .
NB! The complexity of this algorithm depends of a weights distribution of a network.
NB! In some special cases this algorithm may work very slow (see ex 13.1) and moreover,
not terminate.

Example 13.1. Let’s consider several steps of Ford–Fulkerson algorithm:

Figure 40: Steps of Ford–Fulkerson algorithm. First: the flow network G. Second: the flow f
versus capacity among the path (red). Third: the residual network Gf and so on.

Since the path construction algorithm is not specified, the path can be chosen like in this
figure 40 and thus this algorithm will do about 2000 cycles. It is easy to see that by
choosing “right” paths it can be terminated after 2 steps.
To specify the path construction algorithm for example BFS algorithm can be chosen and
corresponded algorithm is called
2. Edmonds–Karp algorithm.
This algorithm finds max-flow in a flow network G from the source s to the terminal t.
Description:
This algorithm works the same as Ford–Fulkerson algorithm but at the step 1b BFS
algorithm is being used for searching the path with the minimum number of edges.
NB! The complexity of this algorithm corresponds to the weights of a network and also
may work very slow.
But the problem of complexity will stay almost the same. The next algorithm solves this
problem:
3. Dinic algorithm.
To explain next algorithm let’s first give some definitions:
Definition 13.9. A level graph corresponded

to the root s of a directed unweight
graph G is a subgraph GL = V (G), EL such that (u, v) ∈ EL ⊂ E(G) ⇐⇒ dist(s, v) =
dist(s, u) + 1.

59
NB! A level graph can be constructed using BFS algorithm starting from the root s.
Note that BF S(v) = dist(s, v), ∀v ∈ V (G).

Definition 13.10. A block flow is the max-flow in the level graph GL corresponded to
the source s.

Statement 4. A level graph is acyclic graph and all paths from the root s to any vertex
v have the same length.

Proof. Easily holds from definition.

Now let’s consider the Dinic algorithm.

Description:
This algorithm finds max-flow in a flow network G from the source s to the terminal t by
using a residual network for a block flow.

(a) Construct GL for a graph G without weights using BFS algorithm. If there is no
path from s to t then terminates.
(b) Construct a block flow f in GL using Edmonds–Karp algorithm.
(c) Do 3a and 3b for the residual network Gf .

Theorem 25 (Block flow). Consider a block flow f . Let’s denote the minimum number
of edges from s to a vertex v in G and in Gf by dist(s, v) and dist′ (s, v) respectively.
Then, dist′ (s, t) ≥ dist(s, t) + 1.

Proof. Let’s denote by len(P ) the length of a path P . First let’s note that if there is
a path P ′ in Gf from s to t then either len(P ′ ) > dist(s, t) or it contains a new edge
e∈/ E(G). Thus it is sufficient to prove that for any path P ′ in Gf from s to t that
/ E(G) the length len(P ′ ) ≥ dist(s, t) + 1.
contains a new edge e ∈
Let’s prove more: if the path P ′ in Gf from s to any vertex v contains new edges
/ E(G) then len(P ′ ) ≥ dist(s, v) + 2k. Let’s prove it using induction by k:
e1 , e2 , ..., ek ∈

(a) The base. If the path P ′ in Gf from s to a vertex v contains a new edge e1 =
(w1 , u1 ) then the inverse edge (u1 , w1 ) belongs to G and f (u1 , w1 ) = c(u1 , w1 ) for
the block flow f . By decomposition algorithm and previous statement there exists
a path in the level graph GL that contains this edge (u1 , w1 ). Thus dist(s, w1 ) =
dist(s, u1 ) + 1.

Let’s denote the part of the path P ′ from the vertex a to b by Pab ′ ′
. Since Psw1
and
′ ′ ′
Pu1 v are paths in G, the length len(Psw1 ) ≥ dist(s, w1 ) and len(Pu1 v ) ≥ dist(u1 , v).
′
Thus len(Psu 1
) ≥ dist(u1 ) + 2 =⇒ len(P ′ ) ≥ dist(s, v) + 2.
(b) Let this statement holds for any j ≤ k − 1 then let’s prove it for j = k. Since
ek = (wk , uk ) is a new edge, there exists a path in the level graph GL that contains
the inverse edge (uk , wk ) and thus dist(s, wk ) = dist(s, uk ) + 1. Since Pu′ k v is a
path in G, the length len(Pu′ k v ) ≥ dist(uk , v).

′
By the induction statement the length len(Psw k
) ≥ dist(s, wk ) + 2(k − 1). Thus
′ ′
len(Psuk ) ≥ dist(s, uk ) + 2k =⇒ len(P ) ≥ dist(s, v) + 2k.

60
 Hence, if a path P ′ in Gf from s to t contains a new edge e ∈
/ E(G) then the length
len(P ′ ) ≥ dist(s, t) + 1.

NB! By the block flow theorem 25 the minimum path length at each step of the Ed-

monds–Karp algorithm increases at least by 1 and thus the number of steps is O ∥V ∥ .
By the decomposition theorem

23 the number of steps in Edmonds–Karp algorithm for a
level graph GL is O ∥V ∥∥E∥ (like
in the decomposition algorithm). Thus the complexity
of Dinic algorithm is O ∥V∥2 ∥E∥ .

NB! One can improve the  complexity of Dinic algorithm using the dynamic tree structure.


In that case it will be O ∥V∥∥E∥ log ∥V∥ .

13.3 Proof of Menger’s theorem

Lemma 42 (Integer flow). If all capacities of a flow network are integer then there exists a
max-flow that is also integer on every edge.

Proof. By using any max-flow construction algorithm one can obtain the integer max-flow.

Lemma 43. If all capacities of a flow network are either 0 or 1 and the max-flow value equal
to K then the paths from the source s to the terminal t are K-edge independent.

Proof. Let’s construct the integer max-flow from the previous lemma. By using decomposi-
tion algorithm any paths Pi will be edge independent and since the flow among each path
equals to 1 then the number of paths Pi equals to K.

Theorem 26 (Menger). A graph is κ-vertex (edge) connected iff. for any two vertices there
exist κ-vertex (edge) independent paths.

Proof. 1. Let’s prove first for edges.

(a) Sufficiency. If there exist κ-edge independent paths thus there is no κ − 1-edge
cuts.
(b) Necessarity. Let the graph G be connected after a deletion of any κ − 1 edges.
Let’s denote two vertices in the condition by s and t. Let’s define weight of every
edge in G by 1. Consider G as the flow network and let f be the max-flow. By the
Ford-Fulkerson theorem 24: F = c(Amin , Bmin ) and equal to the number of edges
from vertices of Amin to vertices of Bmin . Since the graph G will be connected
after a deletion of any κ − 1 edges and F is integer, the value F ≥ κ. Thus by the
previous lemma the paths from s to t are κ-edge independent.

2. Let’s prove the vertex condition.

(a) Sufficiency. The same as for edges.

(b) For necessarity condition let’s give additional definition:
Definition 13.11. Let A and B be two subsets of vertices of the graph G. A
set S ⊂ V (G) is called AB-separator if there is no path in G starting from any
vertex of A and ending in any vertex of B after the deletion of the set S.

61
 Let’s prove that for any A ⊂ V (G) and B ⊂ V (G) if any AB-separator consist of
at least κ vertices then there exist κ-vertex independent paths from vertices of A
to vertices B (let paths can also be consisted of just one vertex). Let’s prove it by
the induction of the number of edges in G:
T
i. The base. If G has no edges then the vertices in A B are also paths.
ii. Let the induction statement holds for the graph G′ = G \ (v1 , v2 ). Let’s
prove it for G. Let’s assume that AB-separator in G consists of κ vertices.
If AB-separator in G′ consists also of κ vertices then by the induction state-
ment there exist κ-vertex independent paths. Thus there exists AB-separator
S in G′ that consists of κ − 1 vertices. Let v1 (without loss of generality) is
reachable from some vertex of A in G′ \S (otherwise S is a AB-separator in G).
S
Let’s denote this set S {v1 } by S1 . The set S1 is AB-separator in G (other-
wise S is not a AB-separator in G′ ). The AS1 -separator is also AB-separator
in G and thus consists of at least κ vertices. Thus by the induction statement
there exist κ-vertex independent pathsS from vertices of A to vertices S1 . By
providing the same proof for S2 = S {v2 } one can obtain κ-vertex indepen-
dent paths in G from vertices of S2 to B. Since ∥S1 ∥ = ∥S2 ∥ = κ, there exist
κ-vertex independent paths from A to B in G.

13.4 Minimum-cost flow

Definition 13.12. A cost function a is any function a : V (G) × V (G) → R on a flow network
G. The total cost of the flow f with cost function a is
X
p(G) = a(u, v)f (u, v).
(u,v)∈V (G)×V (G), f (u,v)>0

Definition 13.13. A flow is called min-cost-flow if f has the minimum total cost p among
the all another flows with the flow value F .

Let G be a flow network with a flow f and cost function a.

Lemma 44 (Necessary and sufficient condition of min-cost-flow). A flow f is min-cost-flow iff.

there are no negative cycles corresponding to the cost function a in the residual network Gf .

Proof. 1. Necessarity. Assume the contrary: there exists negative cycle C in the residual
network Gf . Let cf,C = mine∈C cf (e). Let’s define a flow

cf,C
 (u, v) ∈ C,
fC (u, v) = −cf,C (v, u) ∈ C,

0 otherwise.


The total cost of f + fC will be less than the total cost of f . This holds contradiction.

2. Sufficiency. Let f be the flow with no negative cycles corresponding to the cost function
a in the residual network Gf and f ′ min-cost-flow among all flows with the flow
P value F .
′ ′
The total cost p(f ) ≤ p(f ). By the subtraction of flows lemma 38: f = f + fCi =⇒
i
p(f ′ ) ≥ p(f ) =⇒ p(f ′ ) = p(f ).

62
Theorem 27. Let f be the min-cost-flow, P be the path with minimum sum of costs among all
paths from the source s to the terminal t in the residual network Gf and cf,P be the minimum
residual capacity among the path P . Let

δ
 (u, v) ∈ P
fδ (u, v) = −δ (v, u) ∈ P , for any δ : 0 ≤ δ ≤ cf,P .

0 otherwise


Then f + fδ is min-cost-flow among all flows with the value F + δ.

Proof. Let g be a min-cost-flow among all flows with value F + δ. Then by the two flows
lemma 37: g = f + f ′ , where f ′ is a P
flow in the
P residual network Gf with a flow value δ. By
the decomposition theorem 23 f ′ = fP′ i + fC′ i .
i i
By previous lemma any cycle Ci is non-negative cycle corresponding to the cost function
a. If Ci is a positive cycle then the total cost of g can be decreased and it holds contradiction.
Thus ∀i and e ∈ Ci hold a(e) = 0. Therefore,
X X X X X
p(f ′ ) = p(fP′ i ) = a(u, v)fP′ i (u, v) = f ′ (Pi ) a(u, v) ≥
i i (u,v)∈Pi i (u,v)∈Pi
X X X
≥ f ′ (Pi ) a(u, v) = δ a(u, v) = p(fδ ).
i (u,v)∈P (u,v)∈P

Before introducing min-cost-max-flow construction algorithm let’s define the flow among a
path P in the residual network by

cf,P
 (u, v) ∈ P,
′
f = −cf,P (v, u) ∈ P,

0 otherwise,


where cf,P is the minimum residual capacity among the path P .

Now, let’s introduce

1. Min-cost-max-flow construction using Ford-Fulkerson algorithm.

Description:

(a) Initialise f = 0.
(b) Find a negative cycle C corresponding to the cost function a in the residual network
Gf using Belman-Ford algorithm.
(c) Increase f by the flow f ′ among the cycle C and go to step 1b.
(d) When there will be no negative cycles in the resulting residual network Gf , find
the path P with minimum sum of costs from the source s to the terminal t in this
network Gf .
(e) Increase f by the flow f ′ among the path P and go to step 1d.

NB! Since this algorithm is a modification of Ford-Fulkerson algorithm, the complexity

is also depends of the distribution of capacities and price function.

2. Min-cost-max-flow construction using Dinic algorithm.

Description:

63
 (a) Find max-flow f using Dinic algorithm.
(b) Find a negative cycle C corresponding to the cost function a in the residual network
Gf using Belman-Ford algorithm.
(c) Increase f by the flow f ′ among the cycle C and go to step 2b.



NB! The complexity of this algorithm is O ∥V∥∥E∥2 + ∥V∥2 ∥E∥ = O ∥V∥∥E∥ ∥E∥ + ∥V∥ .

14 Local and global characteristics of graph

14.1 Centralities with local knowledge
Let’s consider an undirected graph G.

Definition 14.1. Centrality is a function defined for each vertex of a graph that contains
some information of a graph structure.

Let’s denote

• by N (v) the set of vertices which adjacent to a vertex v,

S
• by N (v) = N (v) v,

• by f (x1 , x2 , ..., xk ), where f is any function V × V × ... × V → R the restriction of this

function on N (v) (for example L(x, y) will be the average shortest path between x and y
restricted to subgraph N (v)),

• by di = deg(vi ),

• by n = ∥V (G)∥, m = ∥E(G)∥,

• by X(i) = X(vi ) for any X — set or function corresponding to vertex vi .

First let’s give some general centralities which contain local information of the graph G:

1. The simplest example is the degree centrality di = deg vi = ∥N (i)∥.

2. Let’s denote by G N (v) the induced subgraph

on vertices V N (v) . and by M C(v)
the largest connected component in G N (v) . Maximal neighborhood component
M N C(v) is the number of vertices in M C(v).


E M C(v)
3. Density of maximal neighborhood component DM N C(v) =
ϵ , for some
V M C(v)
ϵ ∈ [1, 2].


number of edges in N (i) 2 E N (i)
4. Local cluster coefficient ci = c(vi ) = maximum possible number of edges in N (i)
= di (di −1)
.

Let’s represent the list of general global characteristics of a graph:

1. The simplest example is diameter diam(G) = maxs,t dist(s, t).

number of edges in G 2m
2. Density D(G) = maximum possible number of edges in G
= n(n−1)
.
1 1
P
3. Global efficiency Eglob (G) = n(n−1) dist(s,t)
.
s̸=t

64
 1
P
4. Average shortest path length L(G) = n(n−1)
dist(s, t).
s̸=t


1
P 1
P 2 E N (i))
5. Average clustering coefficient CW S (G) = n
ci = n di (di −1)
.
i∈V (G) i∈V (G)

6. Global clustering coefficient

P
aij ajk aki
number of closed triplets in G 3×number of triangles G i,j,k∈V (G)
C(G) = number of all triplets in G
= 1 P
di (di −1)
= P
di (di −1)
.
2
i∈V (G) i∈V (G)

CW S (G)
7. Small world coefficient SW (G) = CW S (Gr )
, where Gr is a random graph (n, m).

NB! It turns out that most real life networks are satisfied the small world property SW (G) ≫ 1.

NB! Random graph (n, m) is also called Erdős–Rényi graph.

Often in the literature there is common mistake: the average clustering coefficient or Watts-
Strogatz coefficient CW S (G) is called global clustering coefficient, but they are different in most
cases. Let’s show some examples:
Example 14.1. Consider windmill graph W (n, k) — the graph that is constructed of n copies
of complete graph Kn and one additional vertex that has connections to all vertices of these
graphs. Following by [10] for windmill graphs W (n, k) hold:



1. ∀n, k ≥ 2, CW S W (n, k) > C W (n, k) ,



2. lim CW S W (n, k) = 1, lim C W (n, k) = 0.
n→∞ n→∞

Let’s prove this. First,

k(k−1) k(k−1)(k−2)



3n 2
+ 6 k2 −1
C W (n, k) = 1

= k2 −k+nk−1
.
2
nk2 (k−1)+nk(nk−1)
nk(k−1) k−1
ccentral vertex = nk(nk−1) = nk−1 ,
1 k−1


CW S W (n, k) = nk+1 ( nk−1 + nk) =
2 k 2 −nk
= k−1+n
n2 k2 −1
= 1 − k n2n−1
k2 −1
.


Figure 41: Windmill graph W (3, 5).
Hence, lim CW S W (n, k) = 1, lim C W (n, k) = 0.
n→∞ n→∞

Second, compare the average clustering coefficient and the global clustering coefficient:



CW S W (n, k) ∨ C W (n, k)

k − 1 + n2 k 2 − nk k2 − 1
∨
n2 k 2 − 1 k 2 − k + nk − 1
k 3 n3 − k 3 n2 − k 3 n − k 2 n2 + 2k 2 n + k 3 − k 2 ∨ 0
k 2 (n − 1)2 k(n − 1) − 1 ∨ 0

For n ≥ 2 and k ≥ 2 : k 2 (n − 1)2 k(n − 1) − 1 > 0. Therefore, CW S W (n, k) > C W (n, k) .

65
Example 14.2. Let’s consider wheel graph W (k) — the graph constructed of k-vertex cycle
and one vertex in the

center that
has connections to all vertices
of cycle. If k
= 32 it is easy to
see that CW S W (3) = C W (3) = 1. If k = 4 then CW S W (4) = C W (4) = 3 .
For the case k ≥ 5 holds



1. CW S W (k) > C W (k) ,
2. lim CW S W (k) = 23 , lim C W (k) = 0.



k→∞ k→∞

Let’s prove it. First, let’s calculate for this graph average clustering coefficient and global
clustering coefficient:

3k 6


C W (k) = 1
= k+5 ,
2
6k+k(k−1)
1 2n 2(k2 −k+3)
+ 23 k =



CW S W (k) = k+1 k(k−1) 3(k2 −1)
.

Hence, lim CW S W (k) = 23 , lim C W (k) = 0.

k→∞ k→∞

Second, compare these two coefficients:

Figure 42: Wheel graph W (k).
CW S W (k) ∨ C W (k) ,
2(k2 −k+3) 6
3(k2 −1)
∨ k+5
,
k 3 − 5k 2 − 2k + 24 ∨ 0
(k 2 − k + 3)(k + 5) ∨ 9(k 2 − 1)
(k + 2)(k − 3)(k − 4) > 0



Therefore, CW S W (k) > C W (k) .

Example 14.3. Let’s consider nested triangles graph T (n) with n + 2 triangles — the graph
constructed of 2 outer triangles and n subsequently nested triangles with connections between
correspondent vertices (see figure 14.3). For these graphs:



1. CW S T (n) > C T (n) ,
2. lim CW S T (n) = 16 , lim C T (n) = 0.



n→∞ n→∞

Let’s prove this.

6 1


C T (n) = 1 (36+36n) = 3(n+1) ,

2 1
 
CW S T (n) = 3(n+2) 6 13 + 3n 16 = n+4
6(n+2)
.
Figure 43: Nested triangles graph T (n).
Hence, lim CW S T (n) = 16 , lim C T (n) = 0.



n→∞ n→∞

Compare these two coefficients:

CW S T (n) ∨ C T (n)

n2 + 5n + 4 ∨ 2n + 4
n(n + 3) > 0



Hence, CW S T (n) > C T (n) .

66
 Let’s prove a theorem (following by [7]) about relations between average local and global
clustering coefficient.

Theorem 28. Consider simple graph G. Let’s ∀i, j ∈ V (G), i ≤ j hold di ≤ dj ⇒ ci ≤ cj ,

then
CW S (G) ≤ C(G).

Proof. Consider re-numeration of vertices such that ∀i ≤ j : di ≤ dj . One can rewrite

P
aij ajk aki
j,k∈V (G)
ci = .
di (di − 1)

Indeed,
(
1 if there exists edge between vertices j and k which adjacent to vertex i,
aij ajk aki =
0 otherwise.

Therefore, P
aij ajk aki
1 X j,k∈V (G)
CW S (G) = .
n di (di − 1)
i∈V (G)

1

P
Denote by xi = di (di − 1). The number of edges ∥E N (i) ∥ = 2
aij ajk aki and the
j,k∈V (G)
di (di −1)
maximum number of edges in subgraph N (i) equals to 2
, thus xi ≥ 2, 0 ≤ ci ≤ 1.

Using Chebyshev’s sum inequality (di ≤ dj ⇒ xi ≤ xj and ci ≤ cj ):

! !
1 X 1 X 1 X 1 X 1 X
xi CW S (G) = xi ci ≤ x i ci = aij ajk aki .
n n n n n
i∈V (G) i∈V (G) i∈V (G) i∈V (G) i,j,k∈V (G)

Therefore, P
aij ajk aki
i,j,k∈V (G)
CW S (G) ≤ P = C(G).
di (di − 1)
i∈V (G)

The equality holds when ∀i, j ∈ V (G) : di = dj (i.e. for regular simple graphs) or when
∀i, j ∈ V (G) : ci = cj .

Corollary 13. Let’s ∀i, j ∈ V (G), i ≤ j hold di ≤ dj ⇒ ci ≥ cj , then

CW S (G) ≥ C(G).

The proof is the same as in theorem 28 using Chebyshev’s sum inequality.

Corollary 14. For simple regular graphs G:

CW S (G) = C(G).

We see that for many cases CW S (G) ≥ C(G), but it is not very hard to come up with an
example then CW S (G) < C(G). Consider the complete graph Kn and glue to each vertex cycle
of the length 4. Due to the symmetry by the theorem 28: CW S (G) < C(G).

67
14.2 Centralities with global knowledge
Now let’s provide the list of general centralities contained a global information of an undirected
graph G:
P σst (v)
1. Betweenness centrality BC(v) = σst
, where σst is the total number of shortest
s̸=t̸=v
paths from s to t and σst (v) is the total number of shortest paths which contains vertex
v.
P
2. Let Ts be a shortest path tree with the root s. Bottleneck BN (v) = ps (v), where
s∈V (G)
(
1 if the set of descendants of v in Ts contains more than ∥V (Ts )∥/4 vertices,
ps (v) =
0 otherwise.
1
3. Closeness centrality Clo(v) = P
dist(v,t)
.
t∈V (G)

1
4. Eccentricity centrality EC(v) = maxt∈V (G) dist(v,t)
.
1
P

5. Local efficiency Eloc (G) = n
Eglob N (v) .
v∈V (G)

P

diam(G)+1−dist(v,t)
t∈V (G)
6. Radiality Rad(v) = n−1
.
P
7. Stress Str(v) = σst (v), where σst is the total number of shortest paths from s to t
s̸=t̸=v
which contains vertex v.
Let’s note that if A(G) is the adjacency matrix of G and E(G) is the efficiency matrix,
where (
1
dist(vi ,vj )
i ̸= j,
E = {eij } =
0 otherwise,
then P
ei,j
(vi ,vj )∈E(N (v))
Eglob (N (v)) = .
di (di − 1)
Thus (
0 dist(v1i ,vj ) vi ̸∼ vj ,
A(G) − E(G) =
0 otherwise.
Now let’s prove some relationships between these measures following by [8]:
Theorem 29. L(G) ≥ 2 − D(G).
Proof. Let α be the number of pairs of vertices v, w with dist(v, w) = 2 and β be the number
of pairs of vertices v, w with dist(v, w) ≥ 3 and let’s denote the number of vertices of G by
n and the number of edges by m. Thus 2m + α + β = n(n − 1).
2m
D(G) = ,
n(n − 1)
2m + 2α + tβ
L(G) = , for some t ≥ 3,
n(n − 1)
2m + 2α + tβ 2m + 2(α + β) 4m + 2(α + β) 2m
≥ = − = 2 − D(G).
n(n − 1) n(n − 1) n(n − 1) n(n − 1)

68
Theorem 30. 3 − L(G) ≤ 2Eglob (G) ≤ 1 + D(G).

Proof. Let’s denotations be the same as in the previous theorem.

1. Consider the case: 2Eglob (G) ≤ 1 + D(G).

1 1
2Eglob (G) = (4m + α + 2ϵβ), for some ϵ < ,
n(n − 1) 2
1 1 2m 2m + α + β
(4m + α + 2ϵβ) ≤ (4m + α + β) = + = 1 + D(G).
n(n − 1) n(n − 1) n(n − 1) n(n − 1)

2. Consider the case: 2Eglob (G) ≥ 3 − L(G).

1 2m + 2α + tβ
(4m + α + 2ϵβ) ∨ 3 − ,
n(n − 1) n(n − 1)
4m + α + 2ϵβ ∨ 3(2m + α + β) − 2m − 2α − tβ,
β(2ϵ + t − 3) ≥ 0.

NB! The equality in the previous theorems 29-30 is obtained in the case then diam N (v) ≤ 2
for any vertex v.


Lemma 45. L N (i) = 2 − ci .

Proof.

1 X
L N (i) = dist(s, t) =
di (di − 1)
s,t∈N (i),s̸=t
!
1 X X
= dist(s, t) + dist(s, t) =
di (di − 1)
(s,t)∈E(N (i)) s,t∈N (i),(s,t)∈E(N
/ (i))
!
1
X
= 2∥E N (i) ∥ + dist(s, t) =
di (di − 1)
(s,i),(i,t)∈E(G),(s,t)∈E(G)
/
!
1


= 2∥E N (i) ∥ + 2 di (di − 1) − 2∥E N (i) ∥ = 2 − ci .
di (di − 1)
Note that shortest paths are calculated for L in the whole graph G.

Corollary 15. Eloc (G) = 21 (1 + CW S (G)).

Proof. Let’s give two alternative proofs:

1. Let’s note that D(N (i)) = C(i). By theorem 30:

3 − L(N (i)) ≤ 2Eglob (N (i)) ≤ 1 + D(N (i)),

3 − (2 − ci ) ≤ 2Eglob (N (i)) ≤ 1 + ci ,
note shortest paths are calculated for L and Eglob in the whole graph G. Averaging by
i we obtain equality.

69
 2. Let’s rewrite local cluster coefficient formula:
P
1
(s,t)∈E(N (i))
ci = ,
di (di − 1)
P P P
1+ 1+ 1
1 1 (s,t)∈E(N (i)) (s,t)∈E(N (i)) s,t∈V (N (i)),(s,t)∈E(N
/ (i))
(1 + ci ) = =
2 2 di (di − 1)
1 1
P P P
1+ 2 dist(s,t)
(s,t)∈E(N (i)) s,t∈V (N (i)),(s,t)∈E(N
/ (i)) s,t∈V (N (i))

= = = Eglob N (i) .
di (di − 1) di (di − 1)
Averaging by i we obtain equality.

15 Spectral properties
In this section theorems and lemmas are provided for undirected graphs unless otherwise spec-
ified. Let’s first review some important and well-known results from Linear Algebra.
Theorem 31 (Courant-Fischer-Weyl Theorem). Let A be a symmetric matrix of order n, and
denote by λ1 (A) ≤ λ2 (A) ≤ ... ≤ λn (A) the eigenvalues of A. Let Hk be the collection of all
k-dimensional linear subspaces of Rn . Then
(Ax, x) (Ax, x)
λk (A) = min max = max min
X∈Hk x∈X\{0} (x, x) X ′ ∈Hn−k+1 x∈X ′ \{0} (x, x)

.
Theorem 32 (Cauchy’s Interlacing Theorem [14, 19]). Let A be an n×n symmetric real matrix,
and B is a principle m × m submatrix of A, then the eigenvalues of B interlace the eigenvalues
of A, i.e.,
αk ≤ βk ≤ βk+n−m , k = 1, · · · , m,
where α1 ≤ · · · ≤ αn are the eigenvalues of A, and β1 ≤ · · · ≤ βm are the eigenvalues of B.
Before presenting the following famous Perron-Frobenius Theorem, we give some definitions
for matrices.
Definition 15.1. A square n × n matrix A = (aij ) is called reducible if the indices 1, 2, · · · , n
can be divided into two disjoint nonempty sets i1 , · · · , ik and j1 , · · · , jℓ (with k + ℓ = n) such
that aij = 0 for any i ∈ {i1 , · · · , ik } and j ∈ {j1 , · · · , jℓ }. A square matrix which is not
reducible is said to be irreducible.
Statement 5. The adjacency matrix of a connected graph is symmetric, irreducible, and have
nonnegative entries.
Proof. By the definition of adjacency matrix, it is clear to be symmetric and have nonnegative
entries.
Now we need to check that if the graph is connected, then its adjacency matrix must
be irreducible. Suppose the contrary, that G is connected but A(G) is reducible. Then the
indices 1, 2, · · · , n can be divided into two disjoint nonempty sets i1 , · · · , ik and j1 , · · · , jℓ
(with k + ℓ = n) such that aij = 0 for any i ∈ {i1 , · · · , ik } and j ∈ {j1 , · · · , jℓ }. This means
that there is no edge with one end-point in i1 , · · · , ik and the other end-point in j1 , · · · , jℓ .
Thus, G is not connected, which contradicts to the assumption that G is connected.

70
Theorem 33 (Perron-Frobenius Theorem [14]). Let A ∈ Rn×n be symmetric, irreducible, and
have nonnegative entries. Then A has an eigenvalue λ that is strictly positive. Furthermore, it
has multiplicity one and its corresponding eigenvector ⃗v has strictly positive entries. Moreover,
the largest eigenvalue of A is positive and has multiplicity 1.
The proof is complicate and thus we only give a citation [14] for it.

15.1 Adjacency and Laplacian matrix spectrum

Let’s prove three theorems about the properties of adjacency and Laplacian matrix spectrum
for undirected graphs (following by [15]). Let’s denote by µmin and µmax the minimum and
the maximum eigenvalues of adjacency matrix A(G) respectively. First, let’s notice that since
the graph is undirected, the adjacency matrix is symmetric and thus Hermitian. Therefore,
from the basic knowledge from Linear algebra the set {(Ax, x) : ∥x∥ = 1} is a closed interval
[a, b] ⊂ R, where (·, ·) is the standard scalar product and a = µmin , b = µmax .
If the graph is not empty then
let’s (v1 , v2 ) ∈ E(G) without loss of generality. Hence,
1 1 1 1


(Ax, x) > 0 for x = √2 , √2 , 0, ..., 0 and (Ax, x) < 0 for x = √2 , − √2 , 0, ..., 0 and therefore,
µmin < 0 < µmax .
Let’s denote by dmin and dmax the minimum and maximum degree value of the graph G
respectively and let ∥V (G)∥ = n.
Theorem 34. Consider a connected undirected graph G with adjacency matrix A(G).
1. For every eigenvalue µ of A(G) holds |µ| ≤ dmax .
2. The maximum degree dmax is an eigenvalue of A(G) iff. G is regular graph. If dmax is an
eigenvalue then its multiplicity equals one.
3. If −dmax is an eigenvalue of A(G) then G is regular and bipartite graph.
4. If G is bipartite then for every eigenvalue µ of A(G) : −µ is also an eigenvalue with equal
multiplicity.
5. For the maximum eigenvalue dmin ≤ µmax ≤ dmax .
6. For any induced subgraph H ⊂ G : µmin (G) ≤ µmin (H) ≤ µmax (H) ≤ µmax (G).
Proof. 1. Let’s x = (x1 , x2 , ...xn ) be the eigenvector corresponding to the eigenvalue µ and
xp = maxi |xi |. Let’s normalize this vector x such that xp = 1. Thus,
n
X n
X
|µ| = |µxp | = api xi ≤ api |xi | ≤ dp ≤ dmax .
i=1 i=1

2. Consider x and xp from 1. For any i = 1...n, |xi | ≤ 1. Therefore,

n
X X
µ = µxp = api xi = xi ≤ dp ≤ dmax .
i=1 (p,i)∈E(G)

If dmax is eigenvalue of A(G) then dp = dmax and xq = 1 for any adjacent vertex q
with p. Thus, using the same procedure for xq imply dq = dmax . Since the graph is
connected, it holds for all vertices. Therefore, G is regular graph. The reverse holds
from the fact that the vector j of all ones is an eigenvector of A(G) by 4 property. The
multiplicity of dmax holds from the Perron-Frobenius theorem 33.

71
 P
3. Using 1 and 2 we obtain i∼p xi ≥ −dp ≥ −dmax . Hence for each i ∈ V (G) : i ∼ p
holds xi = −1 and di = dmax . Using the same arguments for neighbours of xi we obtain
∀k ∈ V (G) : k ∼ i holds xk = 1 and dk = dmax (due to normalization of x such that
xi = 1). Therefore, the vertex set V (G) is divided by two groups with xi = 1 and
xi = −1 and there is no edges within each of group. Thus, G is bipartite and regular.
F
4. Let the vertex set divided by two groups V (G) = V1 V2 and there is no edges within
each of group. Consider a map b : Rn → Rn such that ∀x = (xi ) ∈ Rn ,
(
−xi i ∈ V1 ,
b(xi ) =
xi i ∈ V2 .

Let’s show that if µ and
x are eigenvalue

and eigenvector respectively then for any
i ∈ V (G) holds A b(x) i = −µ b(x) i . Indeed, let i ∈ V1 without loss of generality,
then

X X X X X
A b(x) i = aij (−xj ) + aij xj = aij xj = − aij (−xj ) − aij (−xj ) =
j∈V1 j∈V2 j∈V2 j∈V1 j∈V2



= − A(−x) i = −µ(−xi ) = −µ b(x) i .
Therefore, b maps different eigenvectors corresponding to eigenvalue µ to different eigen-
vectors corresponding to eigenvalue −µ. Therefore, these eigenvalues have equal mul-
tiplicity.

5. From 1 holds µmax ≤ dmax . Then,

! n n n
 1  1 1 XX 1X
A √ j ,√ j = aij = di ≥ dmin .
n n n i=1 j=1 n i=1

Thus, µmax = max (Ax, x) ≥ dmin .

x∈Rn :∥x∥=1

6. Let A′ be the adjacency matrix for an induced subgraph H and y ∈ Rn−1 : ∥y∥ = 1,

(Ay, y) = max (Ax, x) = µmax (H).

x∈Rn :∥x∥=1

Consider x = (y, 0) ∈ Rn . Then, ∥x∥ = 1 and (Ax, x) = (A′ y, y) = µmax (H). Hence,
µmax (H) ≤ µmax (G). The other inequality is proved similarly.

Let’s denote by λ1 , λ2 , ..., λn the eigenvalues of Laplacian matrix L for undirected graph G.
Since L is Hermitian matrix the same as adjacency matrix, all eigenvalues will be real and we
can order them: λ1 ≤ λ2 ≤ ... ≤ λn and λ1 = min n
(Lx, x), λn = maxn
(Lx, x). In fact,
x∈R :∥x∥=1 x∈R :∥x∥=1
if x1 ∈ Rn : ∥x1 ∥ = 1 is eigenvector with eigenvalue λ1 , then
(Lx, x)
λ2 = min (Lx, x) = min .
x∈Rn :∥x∥=1,(x,x1 )=0 x∈Rn :(x,x1 )=0 (x, x)
One can continue these procedure for all others eigenvalues. Let’s prove Laplacian matrix
spectrum properties theorem:
Theorem 35 (Laplacian matrix spectrum properties). Consider undirected graph G with n
vertices.

72
 1. ∀x ∈ Rn : (Lx, x) ≥ 0.
2. The first eigenvalue λ1 = 0 and j is eigenvector with eigenvalue λ1 .
3. For the complete graph Kn : λ2 = λ3 = ... = λn = n.
4. For not complete graph λ2 ≤ κ(G), where κ(G) is the connectivity of the graph.
Proof. 1. One can rewrite this as
n 
X X  X
(Lx, x) = di x2i − xi xj = (xi − xj )2 ≥ 0.
i=1 i∼j (i,j)∈E(G)

2. The first part holds from 1 and the second from the property 4 of Laplacian matrix.
3. Let’s do the same procedure like in Cayley theorem 6 for the characteristic polynomial
of Laplacian matrix L of the complete graph Kn . Then, det(L − λI) = −λ(n − λ)n−1 .
Let’s note that by definition κ(Kn ) = n − 1.
4. Let S be aFκ(G)-vertex cut. Denote by H1 and H2 induced subgraphs such that
G\S = H1 H2 and there are no edges between H1 and H2 . Let a = ∥V (H1 )∥ and b =
∥V (H2 )∥. Consider a vector x = (xi ) ∈ Rn such that

b
 i ∈ H1 ,
xi = 0 i ∈ S,

−a i ∈ H2 .


Then (x, j) = 0 and (x, x) = ab2 + ba2 . Denote y = Lx. For the vector j holds Lbj = 0,
therefore y = L(x − bj). Consider i ∈ H1 . Note that

X X
L(x − bj) i = 0 − aki (xi − b) = − (−b) ≤ κb.
k∼i k∈S,k∼i


Analogously if i ∈ H2 then L(x − bj) i
≥ −κa. Therefore,
(Lz, z) (Lx, x) κb2 a + κa2 b
λ2 = min ≤ ≤ = κ.
z∈Rn :(z,j)=0 (z, z) (x, x) ab2 + ba2

Let’s denote the set of edges between subsets U ⊂ V (G) and V \ U by ∂U so-called the
boundary of U . We will give a few words about why it is boundary and so forth in the
section 15.3, but now let’s prove another property of the Laplacian matrix second eigenvalue λ2 :
Theorem 36. Let G be undirected graph with n vertices. Then, ∀U ⊂ V (G) holds
∥U ∥∥V \ U ∥
∥∂U ∥ ≥ λ2 .
n
Proof. Let k = ∥U ∥. Let’s define x = (xi ) ∈ Rn such as
(
n − k i ∈ U,
xi =
k i ∈ V \ U.

Then, (x, j) = 0 and (x, x) = k(n − k)2 + (n − k)k 2 = nk(n − k). Using the equation in 1 in
the previous theorem find (Lx, x) = ∥∂U ∥ n2 . Thus, using the same arguments as in 4 in the
previous theorem obtain the inequality.

73
15.2 The normalized Laplacian spectrum
Let’s define the normalized Laplacian for an undirected unweighted graph G with no loops.
1 1
Definition 15.2. The normalized Laplacian matrix ∆ is defined as D− 2 LD− 2 , where L is
the Laplacian matrix of G, and D = diag(deg v1 , · · · , deg vn ) is the diagonal matrix consisting
of degrees of G. Then 
1, if i = j


∆ij = − √di dj , if i ̸= j, (i, j) ∈ E(G)
1


0, otherwise,
where di = deg vi .
We now list the important properties of ∆:
Theorem 37 (Properties of normalized Laplacian matrix).

1. Consider ∆ as a linear operator ∆ : Rn → Rn , ∆ is self-adjoint with respect to the scalar

product (·, ·), i.e.,
(x, ∆y) = (∆x, y),
for all x, y ∈ Rn and standard scalar product (x, y) := ni=1 xi yi ,
P

2. The operator ∆ is non-negative, i.e., ∀x ∈ Rn ,

(∆x, x) ≥ 0,
√ √
3. For x proportional to ( d1 , · · · , dn ) holds ∆x = 0.

4. tr(∆) = n.
Proof. This properties are easy hold from similar theorem 35 about Laplacian matrix. Let’s
note that for normalized Laplacian
!2
X xi xj
(∆x, x) = √ −p .
(i,j)∈E(G)
di dj

The preceding properties have consequences for the eigenvalues of ∆. We write them as
λk (∆) so that the eigenvalue equation becomes

∆xk = λk (∆)xk ,

with xk being a corresponding eigenvector.

NB! The eigenvalues and eigenvectors of the normalized Laplacian ∆ can be rewritten by
virtue of the (unnormalized) Laplacian in the following component-wise form:

(Lx)i = λdi xi , i ∈ V.

From now on, we work on connected graphs. We can order the eigenvalues of ∆ as

λ1 (∆) = 0 < λ2 (∆) ≤ · · · ≤ λn (∆)

with the < justified by

74
Corollary 16 (Properties of normalized Laplacian matrix spectrum).

1. λi (∆) ≥ 0, ∀i = 1, . . . , n.

2. The smallest eigenvalue is λ1 (∆) = 0. If G is connected, then λk (∆) > 0 for k > 1.

3. n
X
λk (∆) = n.
k=1

Proof. These arguments easily hold from the previous theorem.

Lemma 46. Let Hk be the collection of all k-dimensional linear subspaces of Rn . We have the
following min-max characterization of the eigenvalues:

(∆x, x)
λk = max min
Hk ∈Hk−1 x∈Hk⊥ \{0} (x, x)

and dually

(∆x, x)
λk = min max =
Hk ∈Hk x∈Hk \{0} (x, x)
(∆x, x)
= max min .
Hn−k+1 ∈Hn−k+1 x∈Hn−k+1 \{0} (x, x)

Proof. This is the well-known min-max theorem for the symmetric matrix ∆. Precisely,
taking A = ∆ in Theorem 31, we immediately obtain the desired min-max equalities.

Lemma 47. (a) Any eigenvector x for some eigenvalue λ ̸= 0 satisfies

(∆x, x)
λ= .
(x, x)

(b) The second smallest eigenvalue of ∆ is given by

(yi − yj )2
P
(∆x, x) (i,j)∈E(G)
λ2 = P min
√ = Pmin
di yi2
P
di xi =0 (x, x) di yi =0 i
i∈V i∈V

(c) The largest eigenvalue of ∆ is given by

(∆x, x)
λn = max .
n x∈R \{0} (x, x)

(d) The eigenvalues satisfy

0 ≤ λ ≤ 2.

Proof. (a) It follows from ∆x = λx that

(∆x, x) (λx, x) (x, x)

= =λ = λ.
(x, x) (x, x) (x, x)

75
 √ √
(b) Since ( d1 , · · · , dn ) is an eigenvector corresponding to λ1 = 0, the first equality is
due to min-max theorem of Rayleigh
√ quotient in linear algebra. The second equality is
then followed by taking xi = di yi .

(c) This is also due to min-max theorem of Rayleigh quotient.

(d) Suppose that x is an eigenvector corresponding to λ, then by (a), we have

 2
xj
√xi −√
P
di dj
(∆x, x) (i,j)∈E(G)
λ= = .
x2i
P
(x, x) i∈V

By Cauchy’s inequality,
!2
x2j
 2  X X x2 X x2
X xi xj X xi i
X
√ −p ≤ 2 + =2 =2 di i = 2 x2i
di dj d i dj
i∈V j∈V :j∼i
d i
i∈V
di
i∈V
(i,j)∈E(G) (i,j)∈E(G)

implying that λ ≤ 2.

Theorem 38. Among all the graphs with n vertices, the complete graph has the largest possible
λ2 (∆) and the smallest possible λn (∆).
Pn
Proof.
Pn In fact, since λ 1 (∆) = 0 and the trace i=1 λi (∆) = n, we have (n − 1)λ2 (∆) ≤
n
i=2 λi (∆) = n which means λ2 (∆) ≤ n−1 . The equality holds iff. λ2 (∆) = λ3 (∆) =
n n
· · · = λn (∆) = n−1 . In this case, the eigenvalue n−1 has multiplicity n − 1, and thus
any vector x orthogonal to the the constant vector (1, 1, · · · , 1) (which serves an eigenvector
corresponding to the smallest eigenvalue λ1 (∆) = 0) must be an eigenvector corresponding Pn to
n
λ2 (∆) = λ3 (∆) = · · · = λn (∆) = n−1 . This means that every vector x satisfying i=1 xi = 0
must be an eigenvector. In particular, y = (1, −1, 0, · · · , 0) is an eigenvector corresponding
to n−1 n
. Thus, 1 + √d11 d2 = (∆y,y)
(y,y)
n
= λ = n−1 . This derives d1 d2 = (n − 1)2 , and then together
with di ≤ n − 1, we have d1 = d2 = n − 1. Similarly, we can obtain di = n − 1 for any i,
which means that G is only possible to be a complete graph.

NB! This result indicates that complete graphs can be uniquely characterized by the spectrum
of normalized Laplacian. Below, we show a characterization of multi-partite graphs, meaning
that in some sense, multi-partite graphs can be partially characterized by the spectrum of
normalized Laplacian.

Definition 15.3. An undirected graph is called k-partite iff. one can divide the vertices by
k disjoint groups such that any two vertices from the same group are not adjacent.

In the same way one can define complete k-partite graph:

Definition 15.4. A k-partite graph is called complete k-partite graph if any two vertices
from the different groups are adjacent.

Theorem 39. A graph with λt+1 (∆) > λt (∆) = ... = λ2 (∆) = 1 must be a complete (n − t + 1)-
partite graph, where 2 ≤ t ≤ n − 1.

Proof. Denote by µ1 (A) ≤ · · · ≤ µn (A) the eigenvalues of A ordered non-decreasingly. We

first prove an elementary observation that for any given k = 1, · · · , n, the following statements
hold:

76
 • λk (∆) > 1 iff. µn−k+1 (A) < 0
• λk (∆) < 1 iff. µn−k+1 (A) > 0
• λk (∆) = 1 iff. µn−k+1 (A) = 0
1 1 1 1
In fact, by the relation ∆ = I − D− 2 AD− 2 , it is clear that if D− 2 AD− 2 x = ηx then
1 1
∆x = x−D− 2 AD− 2 x = (1−η)x. This means that 1−η is an eigenvalue of ∆, whenever η is an
1 1 1 1
eigenvalue of D− 2 AD− 2 . Now we write the eigenvalues of D− 2 AD− 2 in non-decreasing order
1 1 1 1 1 1
as η1 (D− 2 AD− 2 ) ≤ · · · ≤ ηn (D− 2 AD− 2 ), and then we have λk (∆) = 1−ηn−k+1 (D− 2 AD− 2 ),
k = 1, · · · , n. By the min-max theorem of Rayleigh quotient, it is clear that for any i =
1, · · · , n,
1 1
− 12 − 21 (D− 2 AD− 2 x, x)
ηi (D AD ) = mini max =
X∈H x∈X (x, x)
xu xv
P
√
deg u·deg v xv
(u,v)∈E(G) yv = deg v
= mini max =
X∈H x∈X x21 + · · · + x2n
P
yu yv
(u,v)∈E(G)
= mini max n ,
X∈H y∈X P
deg v · yv2
v=1
P
yu yv
(u,v)∈E(G)
µi (A) = min max Pn 2
.
X∈Hi y∈X v=1 yv
Since for any y ∈ Rn , the quantity P
yu yv
(u,v)∈E(G)
Pn
deg v · yv2
v=1
lies between
P P
yu yv yu yv
1 (u,v)∈E(G) 1 (u,v)∈E(G)
Pn 2
and Pn 2
.
max deg v v=1 yv min deg v v=1 yv
v∈V (G) v∈V (G)
1 1
From this, we can immediately get that µi (A) > 0 (or < 0) if and only if ηi (D− 2 AD− 2 ) > 0
(or < 0). Indeed, all basic properties for the eigenvalue 0 of an adjacency matrix can be
translated into the language of the eigenvalue 1 of the corresponding normalized Laplacian.
Now, let G be a connected graph which is not complete. If G is not a complete multipartite
graph, then G has three vertices u, v, w such that u ∼ v (i.e., (u, v) ∈ E(G)), (u, w) ̸∈ E(G)
and (v, w) ̸∈ E(G). Consider a shortest path from w to {u, v}, we see that G has two possible
types of induced subgraphs (up to symmetry):
u • u •

w′ w′′ w′ w′′
• • • •

w• w•

v • v •

77
 For the graph on the left hand side (i.e., the path graph on the four vertices u, v, w′ , w′′ ),
the adjacency matrix is  
0 1 0 0
 1 0 1 0 
B1 :=   0 1 0 1 .


0 0 1 0
The characteristic polynomial for this matrix is µ4 − 3µ2 + 1 = (µ2 + µ −√1)(µ2 − µ − 1), thus
the second largest eigenvalue µ3 of the above adjacency matrix is µ3 = 5−1 2
≈ 0.618. While
for the graph on the right hand side (i.e., the graph induced on the four vertices u, v, w′ , w′′ ),
the adjacency matrix is  
0 1 1 0
 1 0 1 0 
B2 :=   1 1 0 1 .


0 0 1 0
The characteristic polynomial for this matrix is µ4 − 4µ2 − 2µ + 1 = (µ + 1)(µ3 − µ2 − 3µ + 1),
thus the second largest eigenvalue µ3 of the adjacency matrix satisfies µ3 ≈ 0.31111 . Since
both of these two graphs on the four vertices u, v, w′ , w′′ have the second largest eigenvalue
larger than 0, and either B1 or B2 is a principle submatrix of A, we have
0 < min{µ3 (B1 ), µ3 (B2 )} ≤ µ3+n−4 (A) = µn−1 (A)
by interlacing (Theorem 32). Thus, λ2 (∆) < 1 which contradicts with the assumption.
Hence, G is a complete multipartite graph.
Suppose that G is a complete multipartite graph on k parts, where k ≥ 2. P Let’s denote
them by V1 , · · · , Vk . Then we find that Ax = 0 for any x with the property that j∈Vi xj = 0,
∀i = 1, · · · , k. Let’s denote by ni = |Vi |. For each Vi the submatrix A(Vj ) has 0 eigenvalue
with multiplicity equal to nj − 1. Thus, 0 is an eigenvalue of A(G) and its multiplicity is
n − k.
Now let’s prove that there is only one positive eigenvalue of A. Suppose that λ > 0 and
Ax = λx. Then ∀j ∈ Vi , i = 1, · · · , k
X
(Ax)j = xv = λxj . (2)
v̸∈Vi

Clearly, xj = xj ′ for any j, j ′ ∈ Vi , and thus for simplicity, we write yi = xj for j ∈ Vi . It

follows from (2) that
k
X X
ni yi = xv = (ni + λ)xj = (ni + λ)yi , ∀j ∈ Vi , i = 1, · · · , k. (3)
i=1 v∈V

Hence, (n1 + λ)y1 = · · · = (nk + λ)yk . Since ni + λ > 0, and there exists i ∈ {1, · · · , k}
such that yi ̸= 0, we have (n1 + λ)y1 = · · · = (nk + λ)yk ̸= 0. Without loss of generality, we
assume (ni + λ)yi = c ̸= 0, ∀i. Then yi = c/(ni + λ) and according to (3), we obtain
k k
X X ni
ni yi = c = (ni + λ)yi = c
i=1 i=1
ni + λ

implying that f (λ) = 1 where

k
X ni
f (t) = , t ∈ [0, +∞).
i=1
ni + t
1
It can be calculated using online program, e.g. [Link]

78
 Clearly,
k
′
X ni
f (t) = − < 0, ∀t ≥ 0,
i=1
(ni + t)2
Since f is continuous and strictly decreasing on [0, +∞), f (0) = k ≥ 2 and limt→+∞ f (t) = 0,
there is a unique point λ ∈ (0, +∞) satisfying f (λ) = 1. (The root of the equation f (λ) = 1
can be viewed as some kinds of Loomis’s lemma). Therefore, combining Perron-Frobenius
theorem (see Theorem 33) and Statement 5, A has exactly one positive eigenvalue λ whose
multiplicity is 1. Then, we have that λn−1 (A) = · · · = λn−(n−k) (A) = 0 > λk−1 (A), which
derives that λn+1−(k−1) (∆) > λn+1−k (∆) = · · · = λ2 (∆) = 1. Taking k = n − t + 1, we obtain
the desired relation in the theorem.

15.3 Cheeger inequality

We consider a subset S of the vertex set V (G), and its complement S = V (G) \ S. We define
the volume of S as X
vol(S) = dv ,
v∈S

and the boundary measure of S as


|∂S| = E(S, S) = (i, j) ∈ E(G) : i ∈ S, j ̸∈ S .

The reason that we call the set ∂S := {(i, j) ∈ E(G); i ∈ S, j ̸∈ S} the boundary of S is that
each edge (i, j) from ∂S cross both S and S. This property is in the same spirit of boundary
in topology – a point is called a boundary point of a set S if every (closed) neighbourhood of
such point intersects both S and the complement S.
In fact, when we consider a graph G as a one-dimensional simplicial complex [20] (i.e., a set-
family K of V := {1, · · · , n} such that each A ∈ K is a singleton {i} or a set {i, j} of cardinality
2 satisfying if A ∈ K and A1 ⊂ A, then A1 ∈ K), the smallest closed star neighbourhood of
an edge is the collection of its two end-vertices and such edge itself (i.e., for any edge (i, j), its
closed star neighbourhood can be expressed as {{i}, {j}, {i, j}} and since we can identity {i, j}
with (i, j), and identity i with {i}, the neighbourhood will be simply written as {i, j, (i, j)}}
under the graph language). So, every neighbourhood of such edge (i, j) ∈ ∂S intersects both S
and the complement S.

S S S S
• ◦ ◦

NB! Note that in the left picture, in the original topological setting, any small neighbourhood
(marked in orange) of a boundary point intersects the sets S and S. In the same spirit, on the
right picture for the setting of graph, the smallest closed neighbourhood (marked in orange) of
any boundary edge (marked in orange) has one endpoint in S and the other in S.

79
 In the case of normalized Laplacian we can give another estimation for the second eigenvalue
λ2 (∆). Let’s introduce the Cheeger constant

E(S, S)
h := min 
S nonempty proper subset of V min vol(S), vol(S)

Now let us state a strong version of the Cheeger inequality [17]:

Theorem 40. √
1− 1 − h2 ≤ λ2 (∆) ≤ 2h.
Proof. Let the vertex set V be divided into the two disjoint sets U, U of nodes, and let U be
the one with the smaller volume. Let’s define x = (xi ) ∈ Rn such as
(
1, i ∈ U,
xi =
−α, i ∈ U ,
P
for positive α > 0 such that the equation i∈V xi di = 0 holds, that is,
X X
di − α di = 0.
i∈U i∈U
P
Since U is the subset with the larger volume i∈U di , we have α ≤ 1. Thus, for our choice
of x, the quotient becomes
2
 P 

 (i,j)∈E(G) (x i − x j ) 

X
λ2 = min P 2
d x
i i = 0 ≤

 i di xi i



(1 + α)2 E(U, U ) (1 + α)2 E(U, U ) (1 + α) E(U, U )

≤ P P 2
= P P = P ≤
i∈U di + i∈U di α i∈U di + i∈U di α i∈U di
E(U, U ) E(U, U )
≤ 2 P =2 .
i∈U di vol(U )
Since this holds for all such splittings of our graph G, we obtain the upper bound

λ2 ≤ 2h.
P
Next, we turn to the hard part. Let y be an eigenvector corresponding to λ2 . Since i yi = 0
and y ̸= 0, we have {i ∈ V : yi > 0} ̸= ∅ and {i ∈ V : yi < 0} ̸= ∅. Without loss of
generality, we may assume that
X 1X
di ≤ di .
i∈V :yi >0
2 i∈V

Let x be the restriction of y onto {i ∈ V : yi > 0}, that is,

(
yi , for i ∈ V with yi > 0
xi =
0, otherwise.

We shall first prove that

(xi − xj )2
P
(i,j)∈E(G)
R(x) := ≤ λ2 .
di x2i
P
i

80
For i ∈ V with xi > 0,
X X
(Lx)i = (xi − xj ) ≤ (yi − yj ) = λ2 di yi = λ2 di xi ,
j∈V :(i,j)∈E j∈V :(i,j)∈E

meaning that
X X X X
(Lx, x) := (Lx)i xi = (Lx)i xi ≤ λ2 di xi xi = λ2 di x2i .
i∈V i∈V :xi >0 i∈V :xi >0 i∈V

Thus, we have R(x) ≤ λ2 .

Also, it follows from
(xi + xj )2 (xi − xj )2
P P
(i,j)∈E(G) (i,j)∈E(G)
2
=2− = 2 − R(x)
di x2i
P P
i d i xi i

that
2
x2i − x2j (xi − xj )2 (xi + xj )2
 P P P
 (i,j)∈E(G) (i,j)∈E(G) (i,j)∈E(G)

 ≤ = R(x) 2 − R(x) . (4)

2 2 2
P
i d i xi
 P

i di xi

Next we shall use a standard procedure in discrete analysis to show

x2i − x2j
P
(i,j)∈E(G)
≥ h.
di x2i
P
i

In fact, taking Vt = {i ∈ V : x2i > t} with t ≥ 0, and taking M = max x2i , we have
i∈V
Z M Z M X Z M X XZ M X
vol(Vt )dt = di dt = 1t<x2i di dt = 1t<x2i di dt = x2i di ,
0 0 i∈Vt 0 i∈V i∈V 0 i∈V

where (
1, for t < x2i ,
1x2i >t =
0, otherwise,
and
Z M Z M X Z M X
|∂Vt |dt = 1dt = 1x2j ≤t<x2i dt =
0 0 (i,j)∈E(G):i∈Vt ,j̸∈Vt 0 (i,j)∈E(G)
X Z M X
= 1x2j ≤t<x2i dt = x2i − x2j .
(i,j)∈E(G) 0 (i,j)∈E(G)

Now, take t0 ∈ [0, M ] such that

|∂Vt0 | |∂Vt |
= min .
vol(Vt0 ) 0≤t≤M vol(Vt )


Then, vol(Vt0 ) ≤ vol(V0 ) = vol {i ∈ V : xi > 0} ≤ vol(V )/2 which implies vol(Vt0 ) ≤
vol(V \ Vt0 ) and thus
|∂Vt0 | |∂Vt0 | |∂Vt |
h≤  = ≤
min vol(Vt0 ), vol(V \ Vt0 ) vol(Vt0 ) vol(Vt )

81
 for any 0 ≤ t ≤ M . So,
|∂Vt | ≥ vol(Vt )h
and hence Z M Z M
|∂Vt |dt ≥ h vol(Vt )dt.
0 0
Therefore, together with all the above facts, we get

x2i − x2j
P
RM
(i,j)∈E(G) |∂Vt |dt
P 2
= R M0 ≥ h.
i d i xi 0
vol(V t )dt

By (4), we have
R(x) 2 − R(x) ≥ h2

which implies √ √
1− 1 − h2 ≤ R(x) ≤ 1 + 1 − h2 .
We finally obtain √
λ2 ≥ R(x) ≥ 1 − 1 − h2 .
The whole proof is then completed.
 2
2 h2
Note that 0 ≤ h ≤ 1, and this yields 0 ≤ 1 − h ≤ 1 − which is equivalent to
2
2
√
h /2 ≤ 1 − 1 − h2 . Then, by the strong Cheeger inequality in Theorem 40, we immediately
obtain the usual Cheeger inequality h2 /2 ≤ λ2 .

16 Graph p-Laplacian
To illustrate the p-Laplacian on graphs, we need to recall the formulation of the classical p-
Laplacian Lp acting on a smooth function f :

Lp f = −div |∇f |p−2 ∇f

where ∇ and div represent the gradient operator and the divergence operator, respectively.
Let G = (V, E) be a finite, undirected, simple graph with n vertices and m edges. Along
this spirit, we define the gradient ∇ : C(V ) → C(E) as



∇x [i, j] = xj − xi ,

where
C(V ) := {real-valued functions on V } ∼
= Rn
and
C(E) := {real-valued functions on E} ∼
= Rm .
Now we can think of an undirected graph G as a directed graph with two orientations, denoted
by [i, j] and [j, i], on each edge {i, j}. And we shall fix an orientation. A vector field ψ is a
map ψ : E → R with the property ψ([i, j]) = −ψ([j, i]) for every i ∼ j. Note that this concept
is similar to the flow introduced in Section 13.
The divergence div : C(E) → C(V ) is defined by
X
divψ(i) = ψ([i, j]).
j∈V :j∼i

82
We remark here that due to the anti-symmetry of ψ, for any nonempty proper subset S ⊂ V ,
X
divψ(S) := ψ([i, j])
(i,j)∈E(G):i∈S,j̸∈S

indicates the ‘rate of flow’ from S to its complement V \ S. That is the reason why we call div
the divergence on graphs.
For p > 1, the graph p-Laplacian Lp : C(V ) → C(V ) is defined by

Lp x = −div(|∇x|p−2 ∇x).

Clearly, if p = 2, we obtain L2 x = −div(∇x) which is indeed the standard Laplacian matrix.

Let ϕp : R → R be defined via ϕp (t) = |t|p−2 t. Then
X
(Lp x)i = ϕp (xi − xj ), ∀i ∈ V.
j∈V :j∼i

By setting δ = ∇ and δ ∗ = −div, we have

Lp = δ ∗ ϕp δ.

It should be noted that δ = B is actually the incidence matrix of G, and the adjoint operator
δ ∗ is the transport B ⊤ .

16.1 Unnormalized version of the p-Laplacian eigenproblem

We say (λ, x) ∈ R × (C(V ) \ {0}) is an eigenpair, if it satisfies the eigen-equation

Lp x = λ ϕp (x)

i.e., X
ϕp (xi − xj ) = λ ϕp (xi ), i ∈ V. (5)
j∈V :j∼i

The eigenvalues / eigenfunctions (also called eigenvectors) of Lp are the critical values / critical
points of the p-Rayleigh quotient

|xi − xj |p
P
p
∥∇x∥p (i,j)∈E(G)
Rp (x) = p := P p
∥x∥p i∈V |xi |

For p = 1, the eigen-equation for L1 reduces to the differential inclusion:

X X
0 ∈ ∂x |xi − xj | − λ ∂x |xi |.
(i,j)∈E(G) i∈V

And inspired by this inclusion condition, we define

X
L1 x := ∂x |xi − xj | = lim Lp x̂
p→1,x̂→x
(i,j)∈E(G)

i.e., the limit points of Lp x̂ for p tends to 1, and x̂ tends to x. However, for the sake of brevity
in this section, we focus only on Lp when p > 1.

83
Statement 6. If x is an eigenvector corresponding to a nonzero eigenvalue of Lp , then
n
X
ϕp (xi ) = 0.
i=1

Proof. Since (λ, x) is an eigenpair of Lp with λ ̸= 0,

X
ϕp (xi − xj ) = λ ϕp (xi ), i = 1, · · · , n.
j∈V :j∼i

Summing up the above n equations, we get

X X X
ϕp (xi − xj ) = λ ϕp (xi ).
i∈V j∈V :j∼i i∈V

Note that the left hand side equals

X

ϕp (xi − xj ) + ϕp (xj − xi ) = 0
(i,j)∈E(G)

where we used the easy fact that ϕp (t) + ϕp (−t) = 0, ∀t ∈ R. This implies that the right
hand side is zero, and thus by λ ̸= 0, we have
X
ϕp (xi ) = 0.
i∈V

Statement 7. For any eigenvalue λ of Lp , λ ≤ 2p−1 d where d is the maximum degree of the
graph. The equality λ = 2p−1 d holds iff. G has a regular bipartite component containing a
vertex realizing the maximum degree.

Proof. Since |xi − xj |p ≤ 2p−1 (|xi |p + |xj |p ), we have

X (∗) X X (∗∗) X
|xi − xj |p ≤ 2p−1 (|xi |p + |xj |p ) = 2p−1 di |xi |p ≤ d2p−1 |xi |p .
(i,j)∈E(G) (i,j)∈E(G) i∈V i∈V

The first inequality (*) holds iff. xi = −xj for any (i, j) ∈ E(G), iff. G has a bipartite
connected component.
The second inequality (**) holds iff. di = d for any i ∈ V with xi ̸= 0. Combin-
ing
P the above factsp on the equality case for (*) and (**), we get that the whole equality
p−1 p
P
(i,j)∈E(G) |xi − xj | = d2 i∈V |xi | holds iff. G has a regular bipartite component that
contains vertices attaining maximum degree. It then follows from

|xi − xj |p
P
(i,j)∈E(G)
λ = Rp (x) = P
|xi |p
i∈V

that the desired conclusion in the statement is true.

Finally, we shall compute the p-Laplacian eigenvalues of complete graphs. This was done
in a paper by Amghibech [16], but the original computation contains a small mistake. Here we
present a corrected proof.

84
Theorem 41. Let G = (V, E) be a complete graph with V = {1, · · · , n}. Then the nonzero
1 1
eigenvalues of Lp are n − α − β + (α p−1 + β p−1 )p−1 , where α, β ∈ Z+ with α + β ≤ n.

Statement 8. Under the above setting, if A and B are two disjoint nonempty subsets of V ,
then there exist a > 0 and b > 0 such that a⃗1A − b⃗1B is an eigenvector corresponding to the
1 1
eigenvalue n − |A| − |B| + (|A| p−1 + |B| p−1 )p−1 of Lp .

Proof. Note that if a⃗1A − b⃗1B is an eigenvector of Lp , the corresponding eigenequation (5)
can be written in component-wise form as

p−1
|B|(a + b)
 + (n − |A| − |B|)ap−1 = λap−1
|B|bp−1 − |A|ap−1 = 0

|A|(a + b)p−1 + (n − |A| − |B|)bp−1 = λbp−1 .


1 1
By solving the equations above, we determine a, b, λ as follows: a = c|B| p−1 , b = c|A| p−1 and
1 1
λ = n − |A| − |B| + (|A| p−1 + |B| p−1 )p−1 , where c ̸= 0.

Statement 9. If x is an eigenvector corresponding to a positive eigenvalue of Lp , then there

exist disjoint nonempty subsets A, B ⊂ V , and a, b > 0, such that x = a⃗1A − b⃗1B .

Proof. Let (λ, x) be an eigenpair with λ > 0. Without of loss of generality, we may assume
x1 ≤ · · · ≤ xn due to the complete symmetry of G.
By Statement 6, there exists 1 ≤ α < β ≤ n such that

x1 ≤ · · · ≤ xα < 0 = xα+1 = · · · = xβ−1 = 0 < xβ ≤ · · · ≤ xn .

Then, the eigenequation (5) becomes

 Pi xk p−1
+ nk=i (1 − xxki )p−1
P
λ = −
 k=1 (−1 + xi ) for i = 1, · · · , α
λ = ik=1 (1 − xxki )p−1 − nk=i (−1 + xxki )p−1
P P
for i = β, · · · , n (6)
Pα
− nk=α+1 xp−1
 p−1
P
k=1 (−xk ) k =0

We shall prove that x1 = · · · = xα , and we split the rest of the proof into two cases:

• p>2
In this case, we use the above equations to express λ for i = α and for i = 1.
n
i=1 in (6) X xk p−1
λ ======= (1 − )
k=1
x1
α n
X xk xk p−1 X xk
≤ ( − ) + (1 − )p−1 (7)
k=1
xα x1 k=α+1
x1
n n
X xk xk p−1 X xk
= ( − ) + (1 − )p−1 (8)
k=α+1
x1 xα k=α+1
x1
n
X xk p−1
≤ (1 − ) (9)
k=α+1
xα
α n
X xk p−1 X xk i=α in (6)
≤− (−1 + ) + (1 − )p−1 ======= λ
k=1
xα k=α+1
xα

85
 where the inequality Pα(7) is due to thePfact that 1 ≤ xk /xα , k = 1, · · · , α, the equality
p−1 n p−1
(8) is because of k=1 (−x k ) = k=α+1 xk , the inequality (7) is based on the
elementary inequality at + bt ≤ (a + b)t whenever a, b > 0, t > 1, in which we take
a = xxk1 − xxαk , b = 1 − xxk1 and t = p − 1. So, all the inequalities are in fact equalities,
which yield
x1 = · · · = xα .
• 1<p<2
In this case, we use the equations in (6) to represent λ when i = α and i = n. We
shall use the elementary inequality at ≥ (a + b)t − bt (or equivalently, at + bt ≥ (a + b)t )
whenever a, b > 0, 0 < t < 1, in which we shall take t = p − 1.
n
i=n in (6) X xk p−1
λ ======= (1 − )
k=1
xn
α α n
X xk xk p−1 X xk p−1 X xk
≥ ( − ) − (−1 + ) + (1 − )p−1 (10)
k=1
xα xn k=1
xα k=α+1
xn
n n α
X xk xk p−1 X xk p−1 X xk
= ( − ) + (1 − ) − (−1 + )p−1 (11)
k=α+1
xn xα k=α+1
xn k=1
xα
n α
X xk p−1 X xk i=α in (6)
≥ (1 − ) − (−1 + )p−1 ======= λ (12)
k=α+1
xα k=1
xα

where the inequality (10) is by (1 − xxnk )p−1 ≥ ( xxαk − xxnk )p−1 − (−1 + xxαk )p−1 for k =
1, · · · , α, the equality (11) is because of αk=1 (−xk )p−1 = nk=α+1 xkp−1 , the inequality
P P
(12) follows from ( xxnk − xxαk )p−1 + (1 − xxnk )p−1 ≥ (1 − xxαk )p−1 . Again, all the inequalities
are actually equalities, which imply x1 = · · · = xα .
If we change x to −x, we obtain that x is constant on {β, β + 1, · · · , n}; this achieves the
proof of the remainder, that is, we have proved that x = a⃗1A − b⃗1B for some a, b > 0, where
A = {1, · · · , α} and B = {β, β + 1, · · · , n}.

Combining Statements 8 and 9, we complete the proof of Theorem 41. It is clear that when
p = 2, all the positive eigenvalues are equal to n.

16.2 Normalized p-Laplacian eigenvalue problem

The normalized p-Laplacian is simply defined by
∆p = D−1 Lp
and the relevant eigenproblem is defined as
∆p x = λ ϕp (x),
which can be written in the component-wise form like (5) as
1 X
ϕp (xi − xj ) = λ ϕp (xi ), i ∈ V.
di j∈V :j∼i

Note that the definition of ∆p involves the inverse of diagonal matrix formed by degrees.
This fact implies that we have to work on graphs with no isolated vertices. That is, we assume
that every vertex is adjacent to some other vertices.
The spectrum of ∆p satisfies the following properties.

86
1. If (λ, x) is an eigenpair of ∆p , then

|xi − xj |p
P
(i,j)∈E(G)
Rp (x) := P =λ
di |xi |p
i∈V

Proof. Multiplying xi by
X
ϕp (xi − xj ) = λ di ϕp (xi )
j∈V :j∼i

and summing up the n equalities over i = 1, 2, · · · , n, we get

X X X
ϕp (xi − xj )xi = λ di ϕp (xi )xi .
i∈V j∈V :j∼i i∈V

Note that the left hand side is

X X X
(ϕp (xi −xj )xi +ϕp (xj −xi )xj ) = ϕp (xi −xj )(xi −xj ) = |xi −xj |p
(i,j)∈E(G) (i,j)∈E(G) (i,j)∈E(G)

while the right hand side is

X X
λ di ϕp (xi )xi = λ di |xi |p
i∈V i∈V

due to the fact that ϕp (t)t = |t|p . The proof is then completed.

2. The eigenvalues of ∆p lie in the interval [0, 2p−1 ].

Proof. For any eigenvalue λ of ∆p , and for any eigenvector x corresponding to λ, we
have
p (∗) p−1 p p
P P
|x − x | 2 (i,j)∈E(G) (|xi | + |xj | ) 2p−1 i∈V di |xi |p
P
(i,j)∈E(G) i j
0≤λ= P p
≤ P p
= P p
= 2p−1 .
d |x
i∈V i i | d
i∈V i i|x | d |x
i∈V i i |

3. The largest eigenvalue is 2p−1 if and only if the graph has a bipartite connected component.
Proof. The first inequality (*) reduces to an equality iff. xi = −xj for any (i, j) ∈ E(G),
iff. G has a bipartite connected component.

87
References
[1] Bondy, J. A. (2008). USR Murty Graph Theory. Graduate Texts in Mathematics, 244.
[2] XU, Y. (2017). KURATOWSKI’S THEOREM.
[3] Patrignani, M. (2013). Planarity Testing and Embedding.
[4] Tutte, W. T. (1956). A theorem on planar graphs. Transactions of the American Mathe-
matical Society, 82(1), 99-116.
[5] Thomassen, C. (1983). A theorem on paths in planar graphs. Journal of Graph Theory,
7(2), 169-176.
[6] KENDALL, M. STEINITZ’THEOREM FOR POLYHEDRA.
[7] Tuzhilin, M. (2024). Relations between average clustering coefficient and another central-
ities in graphs. arXiv preprint arXiv:2407.18275.
[8] Strang, A., Haynes, O., Cahill, N. D., Narayan, D. A. (2018). Generalized relationships
between characteristic path length, efficiency, clustering coefficients, and density. Social
Network Analysis and Mining, 8, 1-6.
[9] Chin, C. H., Chen, S. H., Wu, H. H., Ho, C. W., Ko, M. T., Lin, C. Y. (2014). cytoHubba:
identifying hub objects and sub-networks from complex interactome. BMC systems biology,
8(4), 1-7.
[10] Estrada, E. (2016). When local and global clustering of networks diverge. Linear Algebra
and its Applications, 488, 249-263.
[11] Cvetković, D., Rowlinson, P., Simić, S. (2009). An Introduction to the Theory of Graph
Spectra (London Mathematical Society Student Texts). Cambridge: Cambridge University
Press.
[12] Bollobás, B. (1998). Random graphs (pp. 215-252). Springer New York.
[13] Raygorodsky, A. M. (2010). Models of random graphs and their applications. Proceedings
of MIPT, 2(4), 130-140.
[14] R. A. Horn and C. R. Johnson, Matrix Analysis, 2 ed., Cambridge Univ. Press, Cambridge,
2012
[15] Bollobás, B. (2013). Modern graph theory (Vol. 184). Springer Science and Business Media.
[16] S. Amghibech, Eigenvalues of the discrete p-Laplacian for graphs. Ars Comb. 67 (2003),
283-302.
[17] F. R. Chung, Spectral graph theory, volume 92, American Mathematical Soc., 1997
[18] A. Grigor’yan, Analysis on fractal spaces and heat kernels, in: Z.-Q. Chen, M. Takeda, T.
Uemura (Eds.), Dirichlet Forms and Related Topics, in: Springer Proceedings in Mathe-
matics & Statistics, vol. 394, Springer, Singapore, 2022, pp. 143–159.
[19] S. Fisk, A very short proof of Cauchy’s interlace theorem for eigenvalues of Hermitian
matrices, Amer. Math. Monthly 112 (2005), no. 2, 118.
[20] R. Forman, Morse theory for cell complexes, Advances in Mathematics, 134 (1998), 90–145.

88