Lecture 1
Graph: formally: G(V, E) where V is the set of nodes/vertices/points and E is a set of pairs of vertices.
For convenience, write uv for the edge instead of {u, v}.
If e ∈ E and e = uv then we say that u and v are incident.
If G is a graph, then we call V (G) the vertex set and E(G) the edge set. Also v(G) = |V (G)| and
e(G) = |E(G)|.
uv is an edge, then we say u and v are neighbours. We denote the set of all neigbours N (v) := {u ∈
V |uv ∈ E}.
Degree deg(v) = |N (v)|.
H is a subgraph of G if V (H) ⊆ V (G) and E(H) ⊆ E(G). Notation: H ⊆ G
Walk in G is a sequence v0 , v1 . . . , vn such that vi−1 vi ∈ E for all 0 ≤ i ≤ n.
A path is a walk with v0 , . . . , vn are distinct.
A closed walk is a walk with v0 = vn .
A cycle is a closed walk with v0 , . . . , vn−1 distinct, n ≥ 3
G is a connected graph if for all u ̸= v ∈ V (G), there exists a path from u to v. The graph G = {{a}, ∅}
is connected as well.
The component of G is a maximal connected subgraph. Maximal means we cannot add anything without
becoming disconnected
G is connected if and only if there is only one maximal connected subgraph.
Side remark: multigraph can have more than one edge per pair of vertices. this is not allowed on ’regular’
graphs.
Problem: note that there exists a vertex of odd degree. call it v.
Suppose there exists such a walk (an euler tour or euler circuit, where each edge is used exactly once and
each vertex is visited). If v is not the starting point, then each time we visit v we use 1 edge to enter and
1 edge to leave. This means the number of edges incident with v we use is even. But we must transverse
all edges, so there is 1 bridge left. Therefor we end up at v. But we did not start at v. Contradiction.
Now suppose v is the starting point, then we use 1 edge to leave and we have an even number of edges
left. For each visit, we must use two edges again. Then we must have one edge to arrive at the endpoint.
This implies that v has an even number of edges. Contradiction.
Conclusion: there is no euler tour.
In general, if G contains a vertex of odd degree or if G is disconnected, then no euler tour exists.
Theorem: A finite G has an euler tour (is eulerian) if and only if all vertices have even degree and G is
connected.
(←) done
(→) Lemma: If G is finite and all degrees are greater or equal to 2 then G has a cycle of length. Proof
of lemma: Let v0 , . . . , vk be a path of the maximum possible length (number of edges in path). Note in
particular that k ≥ 2 as deg(v) ≥ 2 for all v ∈ V (G). We know that deg(vk ) ≥ 2 =⇒ N (vk ) contains a
u ̸= vk−1 . If u ̸∈ {v0 , . . . , vk }, then {v0 , . . . , vk , u} is another path. However we assumed k is maximal.
Thus we must have u ∈ {v0 , . . . , vk } =⇒ u = vp where 0 ≤ p ≤ k − 2. Then vp , vp+1 , . . . , vk , vp is a
cycle.
Proof of eulers theorem: what remains to show is that if G has deg(v)even∀v ∈ V and G is connected,
then there exists an euler tour. By induction:
Let m := e(G). Base case: m = 0 The statement is true for all graphs with 0 edges.
Inductive step. Assume true for every graph with < m edges. For m ̸= 0 there is atleast one edge,
v(G) ≥ 2. Since it is also connected, then deg(v) ≥ 2 for all v ∈ V . then by lemma there exists a cycle
of length ≥ 3, {v0 , . . . , vk }. We then write G\C = (V, E\{vi−1 vi : 1 ≤ i ≤ k}). Then for all v ∈ V ,
degG\C (v) = deg(v) if v not on C and deg(v) − 2 if v is on C. so all the degrees of G\C are even.
Let G1 , . . . , Gr be the connected components of G\C. So each has an euler tour T1 , . . . , T3 by the induc-
tion hypothesis. Go around cycle v0 , . . . , vk and each time I reach a component of G\C that I did not
visit before. Do a detour using euler tour of that component.
Each edge of C is used exactly once hence each edge of G\C is used exactly once thus an euler tour of
G must exist.
A hamilton cycle is a cycle that visits each vertex exactly once.
1
, Lecture 2
A graph is acyclic if it does not contain any cycle. A tree is a graph that is connected and acyclic. A
leaf is a vertex of degree exactly equal to 1.
Lemma: Every tree with at least two vertices has at least two leaves.
Lemma: if T is a tree and v ∈ v(T ) a leaf then T \v is also a tree.
Lemma: If G is connected and contains a cycle C then G\e is connected for every e ∈ E(C).
A subgraph T ⊆ G is called a spanning tree of G if T is a tree and V (T ) = V (G).
Corr: Any connected graph contains a spanning tree.
Theorem: The following are equivalent:
1. T is a tree
2. T is connected and e(T ) = v(T ) − 1
3. T is acyclic and e(T ) = v(T ) − 1.
Theorem: The following are equivalent:
1. T is a tree
2. T is minimally connected; that is, T is connected but for everye ∈ E(T ) the graph T \e is disconnected.
V (T )
3. T is maximally acyclic; that is, T is acyclic for for every e ∈ \E(T ) the graph T ∪ e contains
2
a cycle.
Theorem: T is a tree if and only if for every u ̸= v ∈ V (T ) there is precisely one path between u and v.
Lecture 3
Minimum spanning tree: spanning tree connects all vertices. Minimal has the least edges.
Edge weights w : E → (0, ∞) (costs)
What we want is the connected spanning subgraph of mimumum cost.
H is a spanning subgraph of G if H ⊆ G and V (H) = V (G).
We want spanning trees. If H is a spanning subgraph, not a tree, but connected, then H is a cycle, then
H\e is connected for all e ∈ E(C) so the cost of H is not minimum.
If the road cost is proportional to the euclidian distance, then we may end up with funky stuff (steiner
tree problem). P
H ⊆ G, we write w(H) = e∈E(H) w(e)
Kruskal’s algorithm: Input is a connected graph G = (V, E) and positive weights w : E → (0, ∞).
Assume E = {e1 , . . . , em } enumerated such that e1 has the lowest weight.
Initialization: E0 = ∅.
Iteration: Repeat for i = 1, . . . , m. Ei := E i−1 ∪ {ei } if (V, Ei−1 ∪ {ei }) is acyclic and Ei−1 otherwise.
Output: (V, Em ) is the minimum spanning tree.
Theorem: Kruskal 1956: the Kruskal algorithm returns a minimum spanning tree.
Proof: G arbitrary, connected. w : E(G) → (0, ∞), e1 ≤ e2 ≤ · · · ≤ em as in the algorithm statement.
T will denote the output of the algorithm.
First, we show that T is a tree. Acyclic by construction
connected: suppose T is not connected: T = T1 , T2 , . . . , Tk k ≥ 2. G is connected: there exists a path
from u ∈ V (Ti ) to v ∈ V (Tj ), i ̸= j. One of these steps is between vi ∈ V (T1 ), vi+1 ̸∈ V (T1 ). Thus
e = vi vi+1 ∈ E(G)\E(T ). Then there exists i ≤ j ≤ m such that e = ej . What happened in iteration j?
In other words, is Ej−1 ∪ {ej } acyclic?
Ej ∩ ej ⊆ Em ∩ {ej }. If there is a cycle then T ∪ ej has a cylce? But T ∪ ej has no cycle, because T
consists of components. So the endpoints of ej are in the same component of T . Contradiction =⇒ T
has one component and hence is connected.
Remains to show that w(T ) is as small as possible.
Let T ∗ be some minimal spanning tree of G. Assume for contradiction that w(T ∗ ) < w(T ). We say that
T and T ∗ agree on an edge e if e ∈ E(T ) ∩ E(T ∗) or e ̸∈ E(T ) ∪ E(T ∗).
Let i be such that T and T ∗ agree on e1 , . . . , ei−1 but disagree on ei . Assume that i is as large as
possible: for all spanning trees T ′ , the first index such that T, T ′ disagree on ej satisfies j ≤ i (switching
to a different T ∗ if needed). In other words, no spanning tree agrees with T on e1 , . . . , ei .
Note that ei ∈ E(T )\E(T ∗) or ei ∈ E(T ∗)\E(T ). Can ei ∈ E(T ∗)\E(T )? No. So ei ∈ E(T )\E(T ∗).
2
Graph: formally: G(V, E) where V is the set of nodes/vertices/points and E is a set of pairs of vertices.
For convenience, write uv for the edge instead of {u, v}.
If e ∈ E and e = uv then we say that u and v are incident.
If G is a graph, then we call V (G) the vertex set and E(G) the edge set. Also v(G) = |V (G)| and
e(G) = |E(G)|.
uv is an edge, then we say u and v are neighbours. We denote the set of all neigbours N (v) := {u ∈
V |uv ∈ E}.
Degree deg(v) = |N (v)|.
H is a subgraph of G if V (H) ⊆ V (G) and E(H) ⊆ E(G). Notation: H ⊆ G
Walk in G is a sequence v0 , v1 . . . , vn such that vi−1 vi ∈ E for all 0 ≤ i ≤ n.
A path is a walk with v0 , . . . , vn are distinct.
A closed walk is a walk with v0 = vn .
A cycle is a closed walk with v0 , . . . , vn−1 distinct, n ≥ 3
G is a connected graph if for all u ̸= v ∈ V (G), there exists a path from u to v. The graph G = {{a}, ∅}
is connected as well.
The component of G is a maximal connected subgraph. Maximal means we cannot add anything without
becoming disconnected
G is connected if and only if there is only one maximal connected subgraph.
Side remark: multigraph can have more than one edge per pair of vertices. this is not allowed on ’regular’
graphs.
Problem: note that there exists a vertex of odd degree. call it v.
Suppose there exists such a walk (an euler tour or euler circuit, where each edge is used exactly once and
each vertex is visited). If v is not the starting point, then each time we visit v we use 1 edge to enter and
1 edge to leave. This means the number of edges incident with v we use is even. But we must transverse
all edges, so there is 1 bridge left. Therefor we end up at v. But we did not start at v. Contradiction.
Now suppose v is the starting point, then we use 1 edge to leave and we have an even number of edges
left. For each visit, we must use two edges again. Then we must have one edge to arrive at the endpoint.
This implies that v has an even number of edges. Contradiction.
Conclusion: there is no euler tour.
In general, if G contains a vertex of odd degree or if G is disconnected, then no euler tour exists.
Theorem: A finite G has an euler tour (is eulerian) if and only if all vertices have even degree and G is
connected.
(←) done
(→) Lemma: If G is finite and all degrees are greater or equal to 2 then G has a cycle of length. Proof
of lemma: Let v0 , . . . , vk be a path of the maximum possible length (number of edges in path). Note in
particular that k ≥ 2 as deg(v) ≥ 2 for all v ∈ V (G). We know that deg(vk ) ≥ 2 =⇒ N (vk ) contains a
u ̸= vk−1 . If u ̸∈ {v0 , . . . , vk }, then {v0 , . . . , vk , u} is another path. However we assumed k is maximal.
Thus we must have u ∈ {v0 , . . . , vk } =⇒ u = vp where 0 ≤ p ≤ k − 2. Then vp , vp+1 , . . . , vk , vp is a
cycle.
Proof of eulers theorem: what remains to show is that if G has deg(v)even∀v ∈ V and G is connected,
then there exists an euler tour. By induction:
Let m := e(G). Base case: m = 0 The statement is true for all graphs with 0 edges.
Inductive step. Assume true for every graph with < m edges. For m ̸= 0 there is atleast one edge,
v(G) ≥ 2. Since it is also connected, then deg(v) ≥ 2 for all v ∈ V . then by lemma there exists a cycle
of length ≥ 3, {v0 , . . . , vk }. We then write G\C = (V, E\{vi−1 vi : 1 ≤ i ≤ k}). Then for all v ∈ V ,
degG\C (v) = deg(v) if v not on C and deg(v) − 2 if v is on C. so all the degrees of G\C are even.
Let G1 , . . . , Gr be the connected components of G\C. So each has an euler tour T1 , . . . , T3 by the induc-
tion hypothesis. Go around cycle v0 , . . . , vk and each time I reach a component of G\C that I did not
visit before. Do a detour using euler tour of that component.
Each edge of C is used exactly once hence each edge of G\C is used exactly once thus an euler tour of
G must exist.
A hamilton cycle is a cycle that visits each vertex exactly once.
1
, Lecture 2
A graph is acyclic if it does not contain any cycle. A tree is a graph that is connected and acyclic. A
leaf is a vertex of degree exactly equal to 1.
Lemma: Every tree with at least two vertices has at least two leaves.
Lemma: if T is a tree and v ∈ v(T ) a leaf then T \v is also a tree.
Lemma: If G is connected and contains a cycle C then G\e is connected for every e ∈ E(C).
A subgraph T ⊆ G is called a spanning tree of G if T is a tree and V (T ) = V (G).
Corr: Any connected graph contains a spanning tree.
Theorem: The following are equivalent:
1. T is a tree
2. T is connected and e(T ) = v(T ) − 1
3. T is acyclic and e(T ) = v(T ) − 1.
Theorem: The following are equivalent:
1. T is a tree
2. T is minimally connected; that is, T is connected but for everye ∈ E(T ) the graph T \e is disconnected.
V (T )
3. T is maximally acyclic; that is, T is acyclic for for every e ∈ \E(T ) the graph T ∪ e contains
2
a cycle.
Theorem: T is a tree if and only if for every u ̸= v ∈ V (T ) there is precisely one path between u and v.
Lecture 3
Minimum spanning tree: spanning tree connects all vertices. Minimal has the least edges.
Edge weights w : E → (0, ∞) (costs)
What we want is the connected spanning subgraph of mimumum cost.
H is a spanning subgraph of G if H ⊆ G and V (H) = V (G).
We want spanning trees. If H is a spanning subgraph, not a tree, but connected, then H is a cycle, then
H\e is connected for all e ∈ E(C) so the cost of H is not minimum.
If the road cost is proportional to the euclidian distance, then we may end up with funky stuff (steiner
tree problem). P
H ⊆ G, we write w(H) = e∈E(H) w(e)
Kruskal’s algorithm: Input is a connected graph G = (V, E) and positive weights w : E → (0, ∞).
Assume E = {e1 , . . . , em } enumerated such that e1 has the lowest weight.
Initialization: E0 = ∅.
Iteration: Repeat for i = 1, . . . , m. Ei := E i−1 ∪ {ei } if (V, Ei−1 ∪ {ei }) is acyclic and Ei−1 otherwise.
Output: (V, Em ) is the minimum spanning tree.
Theorem: Kruskal 1956: the Kruskal algorithm returns a minimum spanning tree.
Proof: G arbitrary, connected. w : E(G) → (0, ∞), e1 ≤ e2 ≤ · · · ≤ em as in the algorithm statement.
T will denote the output of the algorithm.
First, we show that T is a tree. Acyclic by construction
connected: suppose T is not connected: T = T1 , T2 , . . . , Tk k ≥ 2. G is connected: there exists a path
from u ∈ V (Ti ) to v ∈ V (Tj ), i ̸= j. One of these steps is between vi ∈ V (T1 ), vi+1 ̸∈ V (T1 ). Thus
e = vi vi+1 ∈ E(G)\E(T ). Then there exists i ≤ j ≤ m such that e = ej . What happened in iteration j?
In other words, is Ej−1 ∪ {ej } acyclic?
Ej ∩ ej ⊆ Em ∩ {ej }. If there is a cycle then T ∪ ej has a cylce? But T ∪ ej has no cycle, because T
consists of components. So the endpoints of ej are in the same component of T . Contradiction =⇒ T
has one component and hence is connected.
Remains to show that w(T ) is as small as possible.
Let T ∗ be some minimal spanning tree of G. Assume for contradiction that w(T ∗ ) < w(T ). We say that
T and T ∗ agree on an edge e if e ∈ E(T ) ∩ E(T ∗) or e ̸∈ E(T ) ∪ E(T ∗).
Let i be such that T and T ∗ agree on e1 , . . . , ei−1 but disagree on ei . Assume that i is as large as
possible: for all spanning trees T ′ , the first index such that T, T ′ disagree on ej satisfies j ≤ i (switching
to a different T ∗ if needed). In other words, no spanning tree agrees with T on e1 , . . . , ei .
Note that ei ∈ E(T )\E(T ∗) or ei ∈ E(T ∗)\E(T ). Can ei ∈ E(T ∗)\E(T )? No. So ei ∈ E(T )\E(T ∗).
2
