CME 305: Discrete Mathematics and Algorithms
1 Basic Definitions and Concepts in Graph Theory
A graph G(V, E) is a set V of vertices and a set E of edges. In an undirected graph, an edge is an
unordered pair of vertices. An ordered pair of vertices is called a directed edge. If we allow multi-sets
of edges, i.e. multiple edges between two vertices, we obtain a multigraph. A self-loop or loop is an edge
between a vertex and itself. An undirected graph without loops or multiple edges is known as a simple
graph. In this class we will assume graphs to be simple unless otherwise stated.
If vertices a and b are endpoints of an edge, we say that they are adjacent and write a ∼ b. If vertex a is
one of edge e’s endpoints, a is incident to e and we write a ∈ e. The degree of a vertex is the number of
edges incident to it.
A walk is a sequence of vertices v1 , v2 , . . . , vk such that ∀i ∈ 1, 2, . . . , k − 1, vi ∼ vi+1 . A path is a walk
where vi 6= vj , ∀i 6= j. In other words, a path is a walk that visits each vertex at most once. A closed walk
is a walk where v1 = vk . A cycle is a closed path, i.e. a path combined with the edge (vk , v1 ). A graph is
connected if there exists a path between each pair of vertices. A tree is a connected graph with no cycles.
A forest is a graph where each connected component is a tree. A node in a forest with degree 1 is called a
leaf.
The size of a graph is the number of vertices of that graph. We usually denote the number of vertices with
n and the number edges with m.
Claim 1 Every finite tree of size at least two has at least two leaves. Furthermore, the number of edges in
a tree of size n is n − 1.
Proof: The first property can be seen by starting a path at an arbitrary node, walking to any neighbor that
has not been visited before. Note that since the number of vertices is at least two, we can not have vertices
of degree zero. After at most n steps, we must reach a vertex v with no unvisited neighbors. The degree of
v can not be larger than one. Otherwise, the graph has a cycle and therefore it is not a tree. We can then
traverse a path starting at v, and the vertex where the path stops must be a second leaf.
We can show the second property by induction. The base case n = 1 is trivial. Any tree of size n > 1 has at
least one leaf. Removing a leaf results in a tree with one less node and one less edge. Therefore, a tree with
n vertices has one more edge than a tree with n − 1 vertices.
Proposition 1 If a graph G(V, E) has any two of the following three properties, it has all three.
1. G is connected.
2. G has no cycles.
3. |E| = |V | − 1.
Therefore, any graph with any two of these properties is a tree.
Proof:
(1), (2) ⇒ (3): Already proved in Claim 1.
(1), (3) ⇒ (2): We prove this by contradiction; assume (1) and (3) hold, but (2) does not hold, i.e., graph G
has a cycle. Consider cycle c in G: we remove one of the edges from cycle c. The graph remains connected.
, 2 CME 305: Discrete Mathematics and Algorithms - Lecture 2
We repeat this procedure until there is no cycle left. The resulting graph G0 (V, E 0 ) is still connected.
Moreover, since we removed at least one edge, E 0 ⊂ E and |E 0 | < |E|. On the other hand, G0 is a connected
graph with no cycle, hence by the first part of the proof, it has |V | − 1 edges, which is a contradiction.
(2), (3) ⇒ (1): We prove this by contradiction; assume (2) and (3) hold, but (1) does not hold, i.e., graph G
is not connected. Consider the connected components of G. In other words, partition V into k > 1 subsets
V1 , ..., Vk such that (i) there is no edge between Vi and Vj for i 6= j and (ii) the graph induced by Vi , that is
G(Vi , Ei ) where Ei = {{u, v} : {u, v} ∈ E, u, v ∈ Vi } is connected. Each Gi is connected and has no cycles,
therefore by the first part of the proof, |Ei | = |Vi | − 1. Since there is no edge between Vi and Vj , i 6= j,
Pk
|E| = i=1 |Ei | = |V | − k < |V | − 1 = |E|, which is a contradiction.
2 Eulerian Circuits
Definition: A closed walk (circuit) on graph G(V, E) is an Eulerian circuit if it traverses each edge in E
exactly once. We call a graph Eulerian if it has an Eulerian circuit.
The problem of finding Eulerian circuits is perhaps the oldest problem in graph theory. It was originated by
Euler in the 18th century; the problem was whether one could take a walk in Konigsberg and cross each of
the four bridges exactly once. Motivated by this, Euler was able to prove the following theorem:
Theorem 1 (Euler, 1736)
Graph G(V, E) is Eulerian iff G is connected (except for possible isolated vertices) and the degree of every
vertex in G is even.
Proof:
“⇒”: assume G has an Eulerian circuit. Clearly, G must be connected, otherwise we will be unable to
traverse all the edges in a closed walk. Suppose that an Eulerian circuit starts at v1 ; note that every time
the walk enters vertex v 6= v1 , it must leave it by traversing a new edge. Hence, every time that the walk
visits v it traverses two edges of v. Thus dv is even. The same is true for v1 except for the first step of the
walk that leaves v1 and the last step that it enters v1 . Again, we can pair the first and last edges in the
circuit to conclude that dv1 is also even.
“⇐”: we prove this by strong induction on the number of nodes. For n = 1, the statement is trivial. Assume
G has k + 1 vertices, it is connected, and all the nodes have even degrees. Pick any vertex v ∈ V and start
walking through the edges of the graph, traversing each edge at most once. Given that all the degrees of
the nodes in G are even, we can only get stuck at v. Remove the circuit of visited edges, c1 , from G; Call
this new graph G0 . Node v is an isolated vertex in G0 therefore any connected component of G0 has at
most k vertices. Moreover, it is easy to see that the degree of nodes in G0 are even (we removed an even
number of edges from each vertex). Thus by the induction assumption, all the connected components of G0
are Eulerain. Now, we have a collection of circuits c1 , . . . , cl . We can merge them into one large circuit in
the following way:
Traverse c1 until it enters a vertex v that is part of a not-yet traversed circuit cj . Then start traversing cj ,
following the same rule. We resume traversing c1 once all the edges in cj has been visited. Note that since
G was connected, we will be able to reach all circuits in this fashion.
Euler’s theorem gives necessary and sufficient condition for whether a graph is Eulerian which can be easily
checked in linear time. Note that this is a “constructive” proof: we explicitly defined an algorithm to find
an Eulerian circuit in the proof. In addition, the algorithm is close to optimal, given that its running time
is at most 2|E| and |E| is an obvious lower bound on the number of operations any algorithm can achieve.
1 Basic Definitions and Concepts in Graph Theory
A graph G(V, E) is a set V of vertices and a set E of edges. In an undirected graph, an edge is an
unordered pair of vertices. An ordered pair of vertices is called a directed edge. If we allow multi-sets
of edges, i.e. multiple edges between two vertices, we obtain a multigraph. A self-loop or loop is an edge
between a vertex and itself. An undirected graph without loops or multiple edges is known as a simple
graph. In this class we will assume graphs to be simple unless otherwise stated.
If vertices a and b are endpoints of an edge, we say that they are adjacent and write a ∼ b. If vertex a is
one of edge e’s endpoints, a is incident to e and we write a ∈ e. The degree of a vertex is the number of
edges incident to it.
A walk is a sequence of vertices v1 , v2 , . . . , vk such that ∀i ∈ 1, 2, . . . , k − 1, vi ∼ vi+1 . A path is a walk
where vi 6= vj , ∀i 6= j. In other words, a path is a walk that visits each vertex at most once. A closed walk
is a walk where v1 = vk . A cycle is a closed path, i.e. a path combined with the edge (vk , v1 ). A graph is
connected if there exists a path between each pair of vertices. A tree is a connected graph with no cycles.
A forest is a graph where each connected component is a tree. A node in a forest with degree 1 is called a
leaf.
The size of a graph is the number of vertices of that graph. We usually denote the number of vertices with
n and the number edges with m.
Claim 1 Every finite tree of size at least two has at least two leaves. Furthermore, the number of edges in
a tree of size n is n − 1.
Proof: The first property can be seen by starting a path at an arbitrary node, walking to any neighbor that
has not been visited before. Note that since the number of vertices is at least two, we can not have vertices
of degree zero. After at most n steps, we must reach a vertex v with no unvisited neighbors. The degree of
v can not be larger than one. Otherwise, the graph has a cycle and therefore it is not a tree. We can then
traverse a path starting at v, and the vertex where the path stops must be a second leaf.
We can show the second property by induction. The base case n = 1 is trivial. Any tree of size n > 1 has at
least one leaf. Removing a leaf results in a tree with one less node and one less edge. Therefore, a tree with
n vertices has one more edge than a tree with n − 1 vertices.
Proposition 1 If a graph G(V, E) has any two of the following three properties, it has all three.
1. G is connected.
2. G has no cycles.
3. |E| = |V | − 1.
Therefore, any graph with any two of these properties is a tree.
Proof:
(1), (2) ⇒ (3): Already proved in Claim 1.
(1), (3) ⇒ (2): We prove this by contradiction; assume (1) and (3) hold, but (2) does not hold, i.e., graph G
has a cycle. Consider cycle c in G: we remove one of the edges from cycle c. The graph remains connected.
, 2 CME 305: Discrete Mathematics and Algorithms - Lecture 2
We repeat this procedure until there is no cycle left. The resulting graph G0 (V, E 0 ) is still connected.
Moreover, since we removed at least one edge, E 0 ⊂ E and |E 0 | < |E|. On the other hand, G0 is a connected
graph with no cycle, hence by the first part of the proof, it has |V | − 1 edges, which is a contradiction.
(2), (3) ⇒ (1): We prove this by contradiction; assume (2) and (3) hold, but (1) does not hold, i.e., graph G
is not connected. Consider the connected components of G. In other words, partition V into k > 1 subsets
V1 , ..., Vk such that (i) there is no edge between Vi and Vj for i 6= j and (ii) the graph induced by Vi , that is
G(Vi , Ei ) where Ei = {{u, v} : {u, v} ∈ E, u, v ∈ Vi } is connected. Each Gi is connected and has no cycles,
therefore by the first part of the proof, |Ei | = |Vi | − 1. Since there is no edge between Vi and Vj , i 6= j,
Pk
|E| = i=1 |Ei | = |V | − k < |V | − 1 = |E|, which is a contradiction.
2 Eulerian Circuits
Definition: A closed walk (circuit) on graph G(V, E) is an Eulerian circuit if it traverses each edge in E
exactly once. We call a graph Eulerian if it has an Eulerian circuit.
The problem of finding Eulerian circuits is perhaps the oldest problem in graph theory. It was originated by
Euler in the 18th century; the problem was whether one could take a walk in Konigsberg and cross each of
the four bridges exactly once. Motivated by this, Euler was able to prove the following theorem:
Theorem 1 (Euler, 1736)
Graph G(V, E) is Eulerian iff G is connected (except for possible isolated vertices) and the degree of every
vertex in G is even.
Proof:
“⇒”: assume G has an Eulerian circuit. Clearly, G must be connected, otherwise we will be unable to
traverse all the edges in a closed walk. Suppose that an Eulerian circuit starts at v1 ; note that every time
the walk enters vertex v 6= v1 , it must leave it by traversing a new edge. Hence, every time that the walk
visits v it traverses two edges of v. Thus dv is even. The same is true for v1 except for the first step of the
walk that leaves v1 and the last step that it enters v1 . Again, we can pair the first and last edges in the
circuit to conclude that dv1 is also even.
“⇐”: we prove this by strong induction on the number of nodes. For n = 1, the statement is trivial. Assume
G has k + 1 vertices, it is connected, and all the nodes have even degrees. Pick any vertex v ∈ V and start
walking through the edges of the graph, traversing each edge at most once. Given that all the degrees of
the nodes in G are even, we can only get stuck at v. Remove the circuit of visited edges, c1 , from G; Call
this new graph G0 . Node v is an isolated vertex in G0 therefore any connected component of G0 has at
most k vertices. Moreover, it is easy to see that the degree of nodes in G0 are even (we removed an even
number of edges from each vertex). Thus by the induction assumption, all the connected components of G0
are Eulerain. Now, we have a collection of circuits c1 , . . . , cl . We can merge them into one large circuit in
the following way:
Traverse c1 until it enters a vertex v that is part of a not-yet traversed circuit cj . Then start traversing cj ,
following the same rule. We resume traversing c1 once all the edges in cj has been visited. Note that since
G was connected, we will be able to reach all circuits in this fashion.
Euler’s theorem gives necessary and sufficient condition for whether a graph is Eulerian which can be easily
checked in linear time. Note that this is a “constructive” proof: we explicitly defined an algorithm to find
an Eulerian circuit in the proof. In addition, the algorithm is close to optimal, given that its running time
is at most 2|E| and |E| is an obvious lower bound on the number of operations any algorithm can achieve.
