1 Graph Theory

1.1 Undirected graphs

Definition 1.1.1. An (undirected) multigraph is an ordered triple (V (G), E(G), ψG )
consisting of
ˆ a finite non-empty set V (G) = {v1 , v2 , . . . , vn } of vertices
ˆ a finite set of edges E(G) = {e1 , e2 , . . . er }
ˆ an incidence function ψG that associates with each edge of E(G) an (unordered)
pair of vertices of V (G).

ν(G) = |V | = n is the number of nodes, ε(G) = |E| = r is the number of edges.

We say that a (multi)graph G is trivial if ν(G) = 1 and ϵ(G) = 0, otherwise it is non-
trivial. We call a (multi)graph G empty if ϵ(G) = 0.

Example 1.1.1. Consider the triple (V (G), E(G), ψG ), where

V (G) = {vs , vt } , E(G) = {e} , ψG (e) = (vs , vt ).

vs e vt

Example 1.1.2.

V (H) = {v1 , v2 , v3 , v4 , v5 } , E(H) = {e1 , e2 , . . . , e8 } ,

ψH (e1 ) = (v1 , v2 ), ψH (e2 ) = (v2 , v3 ), ψH (e3 ) = (v3 , v3 ), ψH (e4 ) = (v3 , v4 )

ψH (e5 ) = (v2 , v4 ), ψH (e6 ) = (v4 , v5 ), ψH (e7 ) = (v2 , v5 ), ψH (e8 ) = (v2 , v5 )

e3

e1 e2
v1 v2 v3
e5
e8 e7 e4

v5 v4
e6

Example 1.1.3.

V (I) = {u, v, w, x, y} , E(I) = {a, b, . . . , h} ,

1
ψI (a) = (u, v), ψI (b) = (u, u), ψI (c) = (v, w), ψI (d) = (w, x)
ψI (e) = (v, x), ψI (f ) = (w, x), ψI (g) = (u, x), ψI (h) = (x, y)

h g
y x u
e
f d a

w v
c

Note that multigraphs H of Example 1.1.2 and I of Example 1.1.3 result in the same dia-
gram even though the multigraphs, i.e. the triples (V (H), E(H), ψH ) and (V (I), E(I), ψI )
are not identical. Later we will see that H and I are isomorphic.

Notation 1.1.1. ˆ A loop is an edge whose end-vertices coincide.

ˆ A multiple edge are edges joining the same pair of vertices.

For many practical applications we can simplify multigraphs to graphs. E.g. by combining
the properties of a multiple edge to one edge and removing loops. Hence one often only
needs to study the simpler structure of a graph:

Definition 1.1.2. A graph is a pair G = (V, E) comprising a finite set V ̸= ∅ and a set
E of two-element subsets of V .

The elements of V are the vertices and the elements of E are the edges. The end vertices
of an edge cannot coincide since the elements of E are two-element subsets of V . Fur-
thermore E is a set and cannot contain the same edge, i.e. the same pair of end vertices,
more than once.
The above definition implies that a graph is a multigraph without loops or multiple
edges. Sometimes a graph is also called a simple graph to emphasise that it has no loops
or multiple edges.

Notation 1.1.2. We denote an edge e by its end vertices a and b as e = ab, or, if this is
e
not unique, by e = a − b.

Definition 1.1.3. ˆ A walk is a sequence of edges (e1 , . . . , en ) and a sequence of

e
vertices (v0 , . . . , vn ) such that ei = vi−1 −i vi .
◦ The vertices v1 , . . . , vn−1 are called intermediate vertices.
◦ v0 and vn are called end-vertices.
◦ n is the length.
e1 e2 en
W : v0 v1 v2 ··· vn .

ˆ A trail is a walk where all ei are distinct. A path is a trail where all vi are distinct.

2
ˆ A walk with v0 = vn is called closed. A closed trail is also called a tour.
ˆ A cycle is a closed trail where all intermediate vertices v1 , . . . , vn−1 are dis-
tinct and n ≥ 3. Since any vertex within a cycle or a trail can be the start
and the end of the corresponding closed walk, cycles and trails are only de-
fined up to cyclic permutations of the sequences of edges/vertices. That is, the
e1 e2 e3 e2 e3 e1
sequences v1 v2 v3 v1 , v2 v3 v1 v2 and
e3 e1 e2
v3 v1 v2 v3 represent one and the same cycle.

Lemma 1.1.1. ˆ Deleting certain edges and vertices from a walk or trail we can
obtain a path from v0 to vn .
ˆ Deleting loops and multiple edges from a multigraph we obtain a graph.

e1 e1
v1 v2 e6 v1 v2

e4 e4 e5
e3 e2 e3 e2
v4 v3 v4 v3
A graph A multigraph

e1 v1 = v4 e5 e6
v0 v6
e1 v1 e2 e3 v5
v0 v3
v2 e4 e2
(e1 , e2 , e3 ) is a path joining v0 to v3 of
length 3 in a graph G v3 v2
e3
(e1 , . . . e6 ) from a trail of length 6.
e2
v1 v2
e1 e3

v0 = v7 v3

e7 e4
v6 v4
e6 v5 e5
(e1 , . . . e7 ) from a cycle of length 7

Definition 1.1.4. ˆ Two multigraphs G and H are identical (written G = H) if

V (G) = V (H), E(G) = E(H), and ψG = ψh .
ˆ Two multigraphs G and H are isomorphic (written G ∼
= H) if there are bijections
θ : V (G) → V (H) and φ : E(G) → E(H) such that ψG (e) = (u, v) if and only if
ψH (φ(e)) = (θ(u), θ(v)).
The pair θ, φ is called an isomorphism between G and H.
ˆ Two graphs G and H are identical (G = H) if V (G) = V (H), E(G) = E(H).

3
ˆ Two graphs G and H are isomorphic (G ∼ = H) if there is a bijection θ : V (G) →
V (H) such that {u, v} ∈ E(G) if and only if {θ(u), θ(v)} ∈ E(H).
θ is called an isomorphism between G and H.

Example 1.1.4. Consider the following multigraphs G and H and graphs I and J.
v2 u v2 u
e1 e2 a b d e1 e2 a b
G: e4 H: I: J:
v1 v3 t v v1 v3 t v
e3 c e3 c

G∼
= H but G ̸= H. An isomorphism is given by the pair of bijections

θ(v1 ) = t, θ(v2 ) = u, θ(v3 ) = v,

φ(e1 ) = a, φ(e2 ) = b, φ(e3 ) = c, φ(e4 ) = d.
Again, I ∼= J but I ̸= J. Now I and J are graphs, since there are no multiple edges
or loops. Hence the edges are uniquely defined by the end vertices. The isomorphism is
then given by the bijection

θ(v1 ) = t, θ(v2 ) = u, θ(v3 ) = v.

In the following we will consider equivalence classes of isomorphic graphs, which can be
represented by unlabelled diagrams.

Definition 1.1.5. ˆ A complete graph is a graph in which each distinct pair of ver-
tices is joined by an edge. For n vertices, there is only one complete graph up to
isomorphism. This graph is denoted by Kn .
ˆ A bipartite graph is a graph whose vertices are partitioned into two subsets X and
Y and whose edges each have one vertex in X and one in Y .
◦ A partition (X, Y ) is called a partition of the graph.
ˆ A complete bipartite graph is a bipartite graph with partition (X, Y ) in which each
vertex of X is joined to each vertex of Y .
◦ Denoted by Km,n where ν(X) = |X| = m and ν(Y ) = |Y | = n.

Definition 1.1.6. A graph G is connected if there is a walk joining any pair of vertices
of G.

For example, the graph below is not connected.

∼
=

4
K5 Cube partitioned into ◦ and •

K3,3 The same cube drawn differently

We can split any graph G into connected subgraphs that are called components. This
corresponds to a partition of the V (G) = V into V1 , V2 , . . . , Vω .

Definition 1.1.7. The subgraphs G(V1 ), G(V2 ), . . . , G(Vω ), where the vertices Vi are
connected, are called the components of G.
ω = ω(G) is the number of components.
Note that ω(G) = 1 if and only if G is connected.

Notation 1.1.3. ˆ Removing a vertex v and all adjacent edges from a graph G results
in a subgraph, denoted by G \ v.
ˆ Removing an edge e from a graph G results in a subgraph, denoted by G \ e.
ˆ A subgraph G′ = (V ′ , E ′ ) of G = (V, E) with V ′ = V is called a spanning subgraph.

c b c b
c b f f
f
g g
g e

h d d a
d a
The graph G \ a is a The graph G \ e \ h is a
A graph G
subgraph of G spanning subgraph of G

Definition 1.1.8. ˆ A vertex v is called a a cut point of a graph G if ω(G) < ω(G\v).
ˆ An edge e is called a cut edge (also called bridge) of G if ω(G) < ω(G \ e).

Note 1.1.1. An edge e of a graph G is a cut edge if and only if e is not contained in a
cycle of G.

5
Example 1.1.5. The two cut points of the left graph and the two cut edges of the right
multigraph are indicted with arrows.
cut points cut edges

Definition 1.1.9. The degree of a vertex v, written deg(v), is the number of adjacent
edges (a loop has two adjacent edges).

Lemma 1.1.2. For a graph with n vertices,

Xn
deg(vi ) = 2 |E| .
i=1

Proof. Each edge has 2 endpoints. ⇒ number P of endpoints of all edges =P2 |E| . But
n n
number of endpoints = sum of all endpoints = i=1 deg(vi ) . ⇒ 2 |E| = i=1 deg(vi )

Corollary 1.1.1. Let G be a graph with ν(G) = n ≥ 2 vertices, none of which are
isolated, and ϵ(G) = n − 1 edges then there exists at least two vertices of degree 1.
P
Proof. From lemma 1.1.2 and ϵ(G) = n − 1 we have v∈V deg(v) = 2ϵ(G) = 2n − 2. No
isolated vertices implies that deg(v) ≥ 1. Now assume i vertices v ∈ V have deg(v) = 1,
then n − i vertices have deg(v) ≥ 2. This leads to a contradiction for i < 2:
X
2n − 2 = deg(v) ≥ 2(n − i) + 1i = 2n − i > 2n − 2 .
v∈V

Lemma 1.1.3. ˆ For a connected graph G, ε(G) ≥ n − 1, where n = ν(G).

ˆ A graph G with ν(G) = n and no cycle has ε(G) ≤ n − 1.

Proof. (i) By induction: For a graph G1 with one vertex, ε(G1 ) ≥ 0.

Now suppose the theorem is true for any connected graph with less than n vertices.
Let Gn be a connected graph with n vertices. Remove some vertex v and adjacent
edges to get the graph Gn \ v. Suppose Gn \ v has ω(Gn \ v) = k components Gn1 ,
Gn2 , . . . , Gnk , where n1 + n2 + · · · + nk = n − 1. Then v had at least least k adjacent
edges, i.e.
ε(Gn ) ≥ ε(Gn \ v) + k
k
X
= ε(Gni ) + k
i=1
= (n1 − 1) + (n2 − 1) + · · · + (nk − 1) + k
=n−k−1+k
= n − 1.

6
(ii) By induction: If n = 1, then E = 0 and the result is obvious.
n − 1 → n: remove edge e = (va , vb ) from G to get H = G \ e. Then H has no path
from va to vb P(otherwise G had a cycle). Then H has k ≥ 2 components H1 , H2 ,
. . . , Hk with ki=1 ν(Hi ) = n, so

ε(G) = ε(G \ e) + 1
k
X
=1+ (ν(Hi ) − 1)
i=1
≤1+n−k
= n − k + 1 ≤ n − 1.

1.2 Trees
Notation 1.2.1. A graph without a cycle is called acyclic

Definition 1.2.1. A tree is connected acycilc graph.

All classes of isomorphic trees with 6 vertices.

Theorem 1.2.1. a. For a tree G we have ε(G) = n − 1 edges, where n is the number
of vertices.
b. A connected graph G with ε(G) = n − 1 edges is a tree, where n is the number of
vertices.
c. An acyclic graph G with ν(G) − 1 = ε(G) edges is a tree, where n is the number of
vertices.

Proof. a. Follows from Lemma 1.1.3.

b. Proof by contradiction: Consider a connected graph G with a cycle and ε(G) =
n−1. Remove an edge e from the cycle. Then G\e is connected and ε(G\e) = n−2,
which contradicts Lemma 1.1.3.

7
c. See Tutorials/Homeworks.

Theorem 1.2.2. Let G be a graph. Then the following conditions are equivalent:
a. G is a tree.
b. G is acyclic, but adding any further edges yields a cycle.
c. Any two vertices are connected by a unique path.
d. G is connected, and any edge of G is a cut edge.

Proof.
a. ⇒ b. Pick a pair of vertices v1 , v2 of G. There exists a path W from v1 to v2 in G since
G is connected.
v W v
1 2

Add another edge between v1 and v2 .

W
e v1 v2
v1 v2 −→
e

The result is a cycle.

b. ⇒ c. Pick vertices v1 , v2 of G. Suppose there is no path between v1 and v2 . Adding an
edge between v1 and v2 cannot yield a cycle, which is a contradiction. Thus G is
connected.
Now suppose there are two distinct paths W and W ′ between v1 and v2 .

W
v1 v2
W′

Then G contains a cycle.

c. ⇒ d. Pick an edge e with vertices v1 , v2 . Suppose G \ e is still connected. Then there
would be two distinct paths from v1 to v2 .
d. ⇒ a. Suppose G is connected and contains a cycle C. Then G \ e would be connected for
any e in C. But then e would not be a cut edge, which is a contradiction. Thus, G
is acyclic.

Definition 1.2.2.
ˆ A subgraph G′ of G with V (G′ ) = V (G) is called a spanning subgraph.
ˆ A spanning subgraph T of G that is a tree is called a spanning tree.

8
Let G′ be a connected spanning subgraph of connected graph G with a simple cycle C.
Removing an edge from G′ that is in C will result in a graph that is again a spanning
subgraph of G.

Corollary 1.2.1. Every connected graph contains a spanning tree.

Proof. Let G be connected and G′ be a connected spanning subgraph of G. If G′ is not

acylic, remove an edge from one of its cycles. Iterate this procedure until G′ is acyclic.
The resulting graph is connected, acyclic and a spanning subgraph and hence a spanning
tree.

Graph G Spanning tree of G Subgraph of G

Theorem 1.2.3. A vertex v of a tree T is a cut point of T if and only if deg(v) > 1.

Proof.
=⇒ If deg(v) = 0, then T = K1 , so v is not a cut point. If deg(v) = 1, then T \ V is
acyclic with ε(T \ v) = ν(T \ v) − 1 edges. Hence T \ v is a tree, so v is not a cut
point.
⇐= If deg(v) ≥ 2, there exist two distinct vertices u and w adjacent to v. The path
u → v → w is a path in T , and must be unique. Hence there is no path u → w in
T \ v, so ω(T \ v) > 1 = ω(G), so v is a cut point.

Corollary 1.2.2. Every nontrivial connected graph G has at least two vertices that are
not cut points.

Proof. G contains a spanning tree T , and T has at least two non cut point vertices vi .
Since T \vi is a spanning tree of G\vi , we must have ω(G\vi ) = ω(T \vi ) = ω(T ) = ω(G).
Thus, vi are not cut points of G.

Definition 1.2.3. An edge e of G is contracted if it is deleted and its end vertices are
identified. The resulting multigraph is denoted by G · e.
e1 e1
v1 v2 v2
e e2
e4 e2 −→ e4 v1 = v3
v4 v3 v4 e3
e3

9
Note 1.2.1. If e is an edge of G, then
ˆ ν(G · e) = ν(G) − 1
ˆ ε(G · e) = ε(G) − 1
ˆ ω(G · e) = ω(G) .
Hence if T is a tree, T · e is a tree.

Definition 1.2.4. Let G be a (multi)graph. Denote by τ (G) the number of spanning

trees of G.

Theorem 1.2.4. If e is an edge of G and not a loop, then τ (G) = τ (G \ e) + τ (G · e).

Proof. τ (G \ e) is the number of spanning trees of G which do not contain e, as such trees
are also spanning trees of G \ e.
τ (G · e) is the number of spanning trees of G that contain e, since there exists a bijection
between the T of G that contain e and T · e of G · e.

We can use Theorem 1.2.4 to calculate the number of spanning trees, but this is inefficient.

Example 1.2.1. Consider the graph e1

G = e2

e3

We can reduce the calculation of τ (G) to the counting of spanning trees by recursively
applying the formula in Theorem 1.2.4 as follows.

G −→ + −→ + +

−→ + + +

And we find τ (G) = 4.

Definition 1.2.5 (Prüfer sequence). Let the vertex set of Kn be N = {1, 2, . . . , n}, n ≥ 2
and T be a spanning tree of Kn . We associate the Prüfer sequence (t1 , t2 , . . . , tn−2 ) as
follows: Regarding N as an ordered set, let s1 be the first vertex of degree one in T ; the
vertex adjacent to s1 is taken as t1 . We now delete s1 from T , denote by s2 the first
vertex of degree one in T \ s1 , and take the vertex adjacent to s2 as t2 . This operation is
repeated until tm−2 has been defined and a tree with just two vertices remains.

10
Note 1.2.2. The reverse procedure is equally straightforward. Observe, first, that any
vertex v of T occurs degT (v) − 1 times in (t1 , t2 , . . . , tn−2 ). Thus the vertices of de-
gree one in T are precisely those that do not appear in this sequence. To reconstruct
T from (t1 , t2 , . . . tn−2 ), we therefore proceed as follows. Let s1 be the first vertex of
N not in (t1 , t2 , . . . tn−2 ); join s1 to t1 . Next, let s2 be the first vertex of N \ {s1 }
not in (t2 , t3 , . . . tn−2 ), and join s2 to t2 . Continue in this way until the n − 2 edges
s1 t1 , s2 t2 , . . . sn−1 tn−2 have been deterimined. T is now obtained by adding the edge join-
ing the two remaining vertices of N \ {s1 , s2 , . . . , sn−2 }. It is easily verified that different
sequences give rise to different spanning trees of Kn . We have thus established the desired
one-one correspondence.
Hence there are nn−2 distinct Prüfer sequences for Kn .

Example 1.2.2. Verify the one-to-one correspondence of Prüfer sequence and tree for
the following tree:

4
←→ (4, 3, 5, 3, 4, 5)
2 3 5 6

7 8

Theorem 1.2.5 (Cayley’s formula). τ (Kn ) = nn−2 .

Proof. To prove the theorem, it suffices to recall the one-to-one correspondence between
the set of spanning trees of Kn and the set of Prüfer sequences.

Example 1.2.3. For K6 we have τ (K6 ) = 64 = 1296 spanning trees. But there are only
6 nonisomorphic spanning trees of K6 .

There also exists a formula for τ (G) for a general graph G in terms of a determinant. For
a typical graph we often find very many different spanning trees. In practical applications
we might want to select a spanning tree according to some additional properties like its
costs, added in the definition of a network. It will be inefficient to compute the costs
of all spanning trees and then compare the costs. We will discuss efficient algorithmic
solutions for this problem later in this course.

1.3 Directed graphs (digraphs)

For real-life applications, e.g. traffic with one-way streets, we also need the notion of
directed links between vertices.

11
Definition 1.3.1. A directed multigraph (or multidigraph) is a triple (V (D), A(D), ψD )
consisting of
ˆ a finite non-empty set V (D) = {v1 , v2 , . . . , vn } of vertices
ˆ a finite set A(D) = {a1 , a2 , . . . , ar } of arcs
ˆ an incidence function ψD that associates with each arc a of A(D) an ordered pair
(vs , vt ) of vertices of V (D) via ψD (a) = (vs , vt ). in such a way that
◦ a joins vs to vt
◦ vs is the starting vertex (tail )
◦ vt is the terminal vertex (head ).

Definition 1.3.2. A directed graph (or digraph) is a pair (V (D), A(D)) of a set V of
vertices and a set A of n ordered pairs (a, b), where a ̸= b are elements of V .

Example 1.3.1.
a1 a2
v1 v2 v3

a4 a3
v4

multigraph : V = {v1 , v2 , v3 , v4 } , A = {a1 , a2 , a3 , a4 }

ψ(a1 ) = (v1 , v2 ) ψ(a2 ) = (v3 , v2 )
ψ(a3 ) = (v4 , v3 ) ψ(a4 ) = (v4 , v2 )

graph : V = {v1 , v2 , v3 , v4 }
A = {(v1 , v2 ), (v3 , v2 ), (v4 , v3 ), (v4 , v3 )}

Thinking of undirected edges as two-way roads and directed arcs as one-way, we can
transform an undirected graph into a digraph by replacing each edge with two arcs with
opposite directions.
v1 v1

v4 v2 v4 v2

v3 v3

Definition 1.3.3. A digraph D′ is a subgraph of a digraph D if

V (D′ ) ⊆ V (D), A(D′ ) ⊆ A(D),

and ψD′ is the restriction of ψD to A(D′ ).

Note 1.3.1. On the relation of directed and undirected graphs

12
ˆ Every (multi)digraph D has an underlying undirected multigraph G obtained by
deleting the directions of the arcs.
ˆ Deleting multiple edges and loops results in the underlying (undirected simple)
graph
ˆ For any graph G we can obtain a digraph by specifying for each edge an order to
its ends.
◦ This digraph D is called the orientation of G.

Definition 1.3.4. A directed walk joining vertex v0 to vn in a digraph D is a sequence

of arcs
a1 = (v0 , v1 ), a2 = (v1 , v2 ), . . . , an = (vn−1 , vn ).
where ψD (ai ) = (vi , vi+1 ), i.e. vi is the tail and vi+1 is the head. A directed trail and path
are directed walks where all arcs respectively arcs and vertices are distinct. A directed
walk is called closed if v0 = vn . A closed directed trail/path is called a directed tour/cycle.

Definition 1.3.5. A vertex v is said to be reachable from vertex u in a digraph D if

there exists a directed (u, v) walk.
ˆ The digraph D is called strongly connected if each vertex is reachable from every
vertex.
ˆ The set of vertices that are reachable from one another are called strongly con-
nected.
ˆ These sets of vertices induce a partition (V1 , V2 , . . . , Vn ) of V (D). The partitions
are the strongly connected components of a digraph D.

Note 1.3.2. Sometimes the word diconnected is used instead of strongly connected.

v2 v2

v1 v3 v4 v7 v1 v3 v4 v7

A digraph D v5 v6 The partition of v5 v6

with V (D) = D with partition
{v1 , v2 , v3 , v4 , v5 , v6 , v7 } {{v1 , v2 , v3 } , {v4 , v5 , v6 } , {v7 }}

Definition 1.3.6. A digraph whose underlying undirected graph is connected is called

connected.

Definition 1.3.7. Let v be a vertex.

ˆ The indegree id(v) of v is the number of arcs with head v
ˆ The outdegree od(v) of v is the number of arcs with tail v

13
Note 1.3.3. The functions id(v) and od(v) have the following properties.
1. id(v) + od(v) = deg(v).
2. For a digraph D with ν(D) = n vertices and ε(D) = r arcs,
n
X n
X
id(vi ) = od(vi ) = r.
i=1 i=1

Definition 1.3.8. A digraph D with vertex set {v1 , v2 , . . . , vn } is specified by the n × n

adjacency matrix
A(D) = A = (aij ),
where aij is equal to the number of arcs from vi to vj .

Example 1.3.2. Consider the multidigraph D on the right:

v1 v2

v4 v3

The 4 × 4 adjacency matrix for D is

   
a11 a12 a13 a14 0 1 0 0
a21 a22 a23 a24  0
  0 0 1
A(D) = 
a31 = .
a32 a33 a34  0 1 0 0
a41 a42 a43 a44 0 0 2 1

The adjacency matrix A has the following properies.

1. The sum over the i-th row is equal to the number of arcs with tail vi .
n
X
aij = ai1 + ai2 + · · · + ain = od(vi )
j=1

2. The sum over the j-th column is equal to the number of arcs with head vj .
n
X
aij = a1j + a2j + · · · + anj = id(vj )
i=1

3. The (i, j) entry of the matrix Ak is the number of directed walks from vertex i to
vertex j of length k. Proof:
ˆ For k = 1 this is the definition of the adjacency matrix.
ˆ Define matrices B and C by

Ak+1 = Ak A = BA = C, so cij = bi1 a1j + bi2 a2j + · · · + bin bnj .

14
Then biℓ aℓj is the number of directed walks from i to ℓ of length k times the
number of directed walks from ℓ to j of length 1, and summing over all ℓ, we
get the sum of all directed walks of length k + 1.
4. We can use A to determine if D is strongly connected as follows.
Compute A, A2 , . . . , An−1 , where n = v(D). If for any pair of indices, there is a
non-zero entry in one of the matrices, then there is a direct walk from vi to vj , so
D is strongly connected. If D is strongly connected, there exists a directed walk
from vi to vj of length ≤ n − 1.
Example 1.3.3.
v1 v2 v3
   
0 1 0 1 0 1
A = 1 0 1 , A2 = 0 2 0
0 1 0 1 0 1

5. An undirected graph corresponds to a symmetric adjacency matrix.

v2  
0 1 1
v1 A = 1 0 1
v3 1 1 0

1.4 Euler Tours and Trails

The problem: find a walk in a graph (network) that goes along each edge.
1. We will find conditions which tell us when it is possible to cover each edge exactly
once. The resulting walk will then be a trail.
2. If it is impossible to cover each edge only once, we will look for a walk which
minimizes the duplication (the Chinese Postman Problem).
Remember that (Definition 1.1.3) a trail in G is a walk where all its edges are distinct.

Definition 1.4.1.
ˆ A trail in G is called Euler trail if it covers all edges of G.
ˆ An Euler trail is called Euler tour if its end-vertices coincide.
ˆ A graph is called Eulerian if it contains an Euler tour.

In the earliest known paper on graph theory (Euler, 1736), Euler showed that it was
impossible to cross each of the seven bridges of Königsberg exactly once during a walk
through the town.
Königsberg bridges problem: (L. Euler, 1736): Cross each bridge exactly once and
return to a starting point.
Any walk in the “Königsberg bridges problem” graph contains no Euler trails.

15
Königsberg bridges

A B

D
The multigraph of the Bridges of Königsberg problem

Lemma 1.4.1. G is a connected (multi)graph, all its vertices are of even degree, and G
contains at least one edge. Then G contains a cycle.

Proof. G cannot be trivial since it contains an edge. If G is nontrivial, G cannot be a

tree since all vertices are of even degree (otherwise contradiction with Corollary 1.1.1).
Hence G must contain a cycle.

Theorem 1.4.1 (Euler’s Theorem). Let G be a connected graph. Then the following
statements are equivalent:
a. G is Eulerian.
b. Each vertex of G has even degree.
c. The edge set of G can be partitioned into cycles.

Proof.
a. ⇒ b. Label the direction of an Euler tour via an arrow on each edge. At each vertex
we have for each incoming arrow an outgoing arrow in our Euler tour. Hence the
degree of each vertex is even.
b. ⇒ c. G contains a cycle C (Lemma 1.4.1). Removing all edges of C from G results in
connected components that have only vertices of even degree. These components
contain cycles and can be partitioned in cycles using induction.
c. ⇒ a. Consider the partition of the edge set of G in cycles. Take one cycle C and associate
with it a closed trail. If this is the only cycle we found an Euler tour (and are
finished), otherwise there must be another cycle that is connected with the closed

16
trail via a vertex v. Join the closed trail with the other cycle at v to form a longer
closed trail. Eventually all cycles are joined and we have an Euler tour.

The Algorithm of Hierholzer constructs an Euler tour:

(1) If G is not connected or contains a vertex with odd degree, STOP: no solution.
(2) Starting from a vertex w0 choose an arbitrary adjacent edge e1 to proceed to the next
vertex. Repeat the process, considering only edges that were not previously chosen.
Eventually, we will return to vertex w0 having constructed a tour T0 = (e1 , . . . , ek ).
Set C0 = T0 and the variable i to 1, i.e. i ← 1.
(3) Consider Gi = G \ Ci−1 . If Gi is empty then Ci−1 is an Euler tour and we STOP.
Otherwise we repeat the following:
(4) Choose a vertex wi that has an adjacent edge in Gi . Construct a tour Ti as in (2)
starting from vertex wi in the connected components of Gi .
(5) Start (and end) the tour Ci at wi and append tour Ti . Denote the resulting tour
by Ci+1 . Increase i by one, i.e. i ← i + 1 and go to (3).

Proof. Existence of Ti in (2): The degree of each vertex in Gi is even (since the degree of
every vertex in Ci−1 is also even). Hence, if we reach a vertex v that is not the starting
vertex wi we can always leave via an edge that has not been previously chosen. Existence
of wi in (4) follows from G being connected.

Example 1.4.1. Construct an Euler tour in G

Theorem 1.4.2. An Euler trail with end-vertices s and t in a connected (non-directed)

graph exists if and only if the degrees of s and t are odd and the degree of all other vertices
are even.

Proof.
⇒ Assume the degrees are as stated. Add an extra edge (t, s). This results in a new
Eulerian graph, since all its vertices are of even degree. Choose an Euler tour where
(t, s) is the last edge. Removing this edge results in an Euler trail.
⇐ Assume the Euler trail exists. Adding the edge (t, s) yields an Euler tour and all
vertices have even degree. Deleting the extra edge again ⇒ All vertices except s
and t have even degree.

Euler tours also exist in directed graphs. Here a relation between the indegree id(v) and
outdegree od(v) of a vertex v plays an important role.

Definition 1.4.2. A vertex v in a digraph is called balanced if id(v) = od(v).

Theorem 1.4.3.
1. An Euler tour in a connected digraph exists if and only if all vertices are balanced.

17
w0

An eulerian (multi)graph G Tour T0

w1

Subgraph G1 = G \ T0 Tour T1 starting from w1

w2 1 6
w2
12 2 5 7

11 14
13 3 4 8
10 9
Final tour T2 in G2 = G1 \ T1 Combine T0 , T1 & T2 to an Euler tour.

2. An Euler trail from vertex s to t in a directed connected graph exists if and only
if each vertex, apart from s and t is balanced, and id(s) = od(s) − 1 and id(t) =
od(t) + 1.

Example 1.4.2. The following picture shows multidigraph where all vertices except s
and t are balanced:

s 1 6
s
12 2 5 7

11
13 3 4 8

t 10 9
t

A multidigraph that allows for an Euler Modify T0 from before to end at t and com-
trail. bine it with T1 & T2 to an Euler trail.

18
1.5 Hamilton cycles
There are many applications where we should consider a tour in a network that visits
every vertex exactly once, e.g. postal collection, delivering of goods, or robotics.

Definition 1.5.1.
ˆ A cycle that visits each vertex of a graph exactly once is called a Hamiltonian cycle.
ˆ A graph G that permits an Hamiltonian cycle is called Hamiltonian.

Given a graph G (with n vertices) and a Hamiltonian cycle H in G, we delete all edges
that are not in H and get a subgraph H with n vertices and n edges.

G H

(a) An Hamiltonian graph G. (b) The Hamiltonian path H of G

Not every graph is Hamiltonian and there exists no simple criterion (that is necessary
and sufficient) to decide if a graph is Hamiltonian or not.

Theorem 1.5.1 (Necessary condition). Let G be Hamiltonian and v1 , v2 , . . . , vk some k

vertices of G. Then ω(G \ {v1 , v2 , . . . vk }) ≤ k.

u v

Figure 1.5.2: Removing a vertex, say u, from a cycle C results in a connected component
C \u. Removing a further vertex, say v, increases the number of components
at most by one.

Proof. Consider a Hamiltonian cycle H of G. Since all edges of H \ {v1 , v2 , . . . vk } are

in G \ {v1 , v2 , . . . vk } we have ω(G \ {v1 , v2 , . . . vk }) ≤ ω(H \ {v1 , v2 , . . . vk }). Since H is
a cycle deg(vi ) = 2 and ω(H \ v1 ) = 1, see Figure 1.5.2. Removing any further vertex
will increase the number of components by at most one. Hence ω(G \ {v1 , v2 , . . . vk }) ≤
ω(H \ {v1 , v2 , . . . vk }) ≤ k.

Corollary 1.5.1. Let G be Hamiltonian, then G is connected.

19
We can rephrase this theorem in the following way: If the Hamiltonian cycle in the graph
G exists and we leave out any k vertices with adjacent edges to the graph G, then the
remaining graph G∗ has at most k connected components.
This implies in particular: If G has a cut point then G is not Hamiltonian. More generally
we could use the following sufficient condition that a graph is not Hamiltonian: “Try
to locate k vertices so that removing them, we obtain more than k connected
components for the remaining graph.”

Example 1.5.1. The graph shown in Figure 1.5.3a admits no Hamiltonian cycles. Delete
two vertices u and v to get three connected components (see Figure 1.5.3b).

v
(a) G is not Hamiltonian (b) G \ u \ v has 3 components.

Theorem 1.5.2. A complete graph Kn with n ≥ 3 has (n − 1)!/2 distinct Hamiltonian

cycles.

Proof. Choose a vertex v0 as a start of the cycle and count number of possible choices
for the edges (e1 , e2 , . . . ei , en ) of the Hamiltonian cycle:
e1 : There are n−1 possible choices of edges (v0 , v1 ) since there are n−1 vertices ∈
/ {v0 }.
e2 : There are n − 2 possible choices of edges (v1 , v2 ) since there are n − 2 vertices
∈
/ {v0 , v1 }.
ei : There are n − i possible choices of edges (vi−1 , vi ) since there are n − i vertices
∈
/ {v0 , v1 , . . . vi−1 }.
en : There is 1 edge (vn−1 , v0 ) that has not been selected if n > 2.
(e1 , e2 , en ) and (en , en−1 , . . . , e1 ) represent the same (undirected) cycle and we have ((n −
1)(n − 2) · · · 1)/2 = (n−1)!2
Hamiltonian tours.

Example 1.5.2. Find all Hamiltonian paths in K4

4 1

3 2

ˆ 1 → 2 → 3 → 4 → 1, (equivalent 1 → 4 → 3 → 2 → 1)

20
ˆ 1 → 3 → 4 → 2 → 1, (equivalent 1 → 2 → 4 → 3 → 1)
ˆ 1 → 4 → 2 → 3 → 1, (equivalent 1 → 3 → 2 → 4 → 1)
ˆ Hence K4 has 3 distinct Hamiltonian cycles.

A particular result for directed graphs

Definition 1.5.2. A directed path in a directed graph that starts from an arbitrarily
chosen vertex and visits every other vertex exactly once is called Hamiltonian path.

Assume that a directed graph D was generated from the complete undirected graph Kn
by assigning directions to all arcs. So, any pair u, v of vertices in D is joined by either
(u, v) or by (v, u).

Proposition 1.5.1. There is a Hamiltonian path in D.

u v1 v2 vn−2 vn−1 v1 v2 vn−2 vn−1 u

(a) u can be attached to v1 to form a di- (b) vn can be attached to u to form a di-
rected path. rected path.
v1 v2 vi−1 vi vn−2 vn−1
v1 v2 vn−2 vn−1

u
u
(d) The arc u → vi is the first instance
(c) u cannot be attached to v1 or vn to form
where the arc points to vi . We can add
a directed path.
u to the directed path.

Figure 1.5.4: A directed path from v1 to vn in the directed graph D.

Proof. We use induction on n. If D has only two vertices a, b then clearly either a → b
or b → a is a Hamiltonian path.
Assume any such D with n − 1 vertices has a Hamiltonian path. Take D with n vertices
and leave out one, say u. The remaining part D′ has n − 1 vertices and admits a
Hamiltonian path (by our assumption). Let this path be v1 → v2 → · · · → vn−1 . The
following possibilities arise.
ˆ Either there is an edge u → v1 (in this case include u as new starting point of the
Hamiltonian path u → v1 → · · · ),
ˆ or there is an edge vn−1 → u (in this case include u as a new terminal vertex in the
path v1 → v2 → · · · → vn−1 → u),
ˆ or we have v1 → u and u → vn−1 (see Figure 1.5.4c ).
For the last case consider vertices v2 , v3 , . . . in turns and locate the first instant i where
an edge u → vi appears (this happens at least at vn−1 ). Then the sequence v1 → v2 →
· · · → vi−1 → u → vi → · · · → vn−1 (see Figure 1.5.4d ) forms a Hamiltonian path.

21
1.6 Planar graphs
Definition 1.6.1. ˆ A graph G is called planar if it can be drawn in the plane so
that its edges intersect only at their endpoints.
ˆ A connected planar graph divides the plane into connected regions called faces.

A graph can be drawn in many ways. For example, Figure 1.6.1 and Figure 1.6.2 are
different representations of the same complete graph K4 . Edges at Figure 1.6.2 have no
crossing. Since K4 admits a representation with no crossings it is planar.

Figure 1.6.1: K4 Figure 1.6.2: K4 drawn differently

Theorem 1.6.1 (Euler’s formula). Let G be a connected planar graph with n vertices, e
edges and f faces, then
f = e − n + 2.

Proof by induction on e.
ˆ If e = 0 then n = 1 (G is connected) and f = 1 (i.e. the whole plane around this
point also called the outer face).
ˆ Consider e > 0
◦ If G has a cycle, remove an edge from the cycle. The resulting graph G has
e′ = e − 1 edges, n′ = n vertices and f ′ = f − 1 faces. From the induction
hypothesis (f ′ = e′ − n′ + 2) we find f = f ′ + 1 = (e′ − n′ + 2) + 1 = e − n + 2
◦ If G is acyclic it is a tree. Then f = 1 (i.e. the outer face extending to infinity)
which is consistent with e − n + 2 = 1 (since e = n − 1 for a tree).

Note 1.6.1. ˆ The proof uses implicitly the Jordan curve theorem for polygons,
which states that any simple closed polygon in the plane divides the plane into two
regions.
ˆ The same formula relates the number of faces, edges, and vertices of polyhedron
(cube, dodecahedron, etc). Their surfaces can be flattened out into the plane with
one face going to the infinite exterior region, i.e. the outer face.
ˆ The same formula (which is often written as f − e + n = 2) applies also for the
graph drawn on the surface of a sphere.

22
The same cube drawn in a plane
Cube drawn as a 3D object

Theorem 1.6.2. The complete graph K5 and bipartite graph K3,3 are not planar.

proof by contradiction:
Assuming that K5 (see Figure 1.6.4), which has n = 5, e = 10, is planar. Then according
to Euler’s formula it would have f = 10 − 5 + 2 = 7 faces when drawn in a plane. Each
face has at least 3 boundary edges (K5 has no multiple edges or loops). Each edge can
be a boundary edge to at most 2 faces. Hence the number of edges e ≥ 7·3 2
= 10.5. This
is a contradiction with e = 10, hence K5 is not planar.
The proof for K3,3 (see Figure 1.6.4) is similar (Tutorials/Homework)

Note 1.6.2.
ˆ A planar graph is still planar if a vertex of degree 2 is added in the middle of an
edge.
ˆ If G contains a non-planar subgraph then it is not planar.

Theorem 1.6.3 (Kuratowski’s theorem). Every non-planar graph contains a subdivided

K3,3 or K5 as a subgraph.

Figure 1.6.4: The complete graph K5 (left) and the bipartite graph K3,3 (right)

23