CHAPTER 8.
The Mathematics of Graph–
Graphs and Euler Circuits
Core Idea
“Mathematics creates connections and fosters efficiency through visual tools like
graphs and algorithms.”
learning objectives
1. define a graph;
2. describe some types and families of graphs;
3. find Euler paths and circuits; and
4. solve real-world problems involving Euler paths
and circuits.
challenge… The Konigsberg Problem
Can you walk through each bridge exactly once?
challenge… The Konigsberg Problem
Can you walk through each bridge exactly once?
6
4
1 5
B D
2 3
7
Historical background
Leonard Euler (1707-1783) – American mathematician
and logician introduced this formal definition of relation
GRAPH THEORY is a branch of mathematics which
illustrates and analyzes connections
between objects.
Applications of Graph Theory
• Biology and Genetics
• Urban Planning
• Finance and Stock Market Analysis
• Telecommunications
• Circuit Design
GRAPH is a set of points called vertices and line
segments or curves called edges.
Two vertices are adjacent if they have a common edge.
Two edges are adjacent if they share a common vertex
A loop is an edge, the endpoints of which are the same vertex.
Multiple edges are two or more edges that are incident to the same two vertices.
1
𝑢
𝑎
loop 𝑒5 𝑒1
𝑦 𝑣 𝑒6
𝑒 5 𝑒7 2
𝑓 𝑒10
𝑏 6
𝑒4 𝑒8
𝑐 𝑒9
𝑥 𝑤 3
multiple 𝑑 4 𝑒3
edges 𝑮 𝑯
GRAPH is a set of points called vertices and line
segments or curves called edges.
Moreover, a graph is simple if it has no loops
or multiple edges. 1
𝑢
𝑎 𝑒5 𝑒1
𝑦 𝑣 𝑒6
𝑒 5 𝑒7 2
𝑓 𝑒10
𝑏 6
𝑒4 𝑒8
𝑐 𝑒9
𝑥 𝑤 4 𝑒3 3
𝑑
𝑮 𝑯
NOT SIMPLE SIMPLE
CONNECTED GRAPH
A graph is connected if there is at least a
path that connects two vertex sets.
𝑬
𝑫 3
1
2 4
𝑭
DISCONNECTED GRAPH
A graph is disconnected if there is no path to
connect two vertex sets.
3
1
2 4
𝑰 𝑱
NULL GRAPH
It is a graph in which no edge is drawn
between any two vertices.
1
5 2
4 3
𝑴 𝑵
COMPLETE GRAPH
It is a graph in which
every possible edge
is drawn between
the vertices.
Moreover, this
implies that any
two vertices are
adjacent.
BIPARTITE GRAPH
A graph is bipartite if it is possible to divide all its vertices
into two disjoint subsets such that every edge in the graph
connects a vertex in one subset to a vertex in the other
subset.
𝑢1 𝑣1
𝑥1 𝑥2 𝑥3
𝑢2 𝑣2
𝑦1 𝑦2 𝑦3 𝑢3 𝑣3
𝑷 𝑸 𝑹
DIRECTED GRAPH It is a graph where all the edges are directed from
one vertex to another.
It is also called a digraph.
𝑫
TREE GRAPH It is an undirected graph in which any two vertices are
connected by exactly one path.
EQUIVALENT GRAPHS
Two or more graphs are equivalent if the edges form the same
connections of vertices.
𝑷 𝑸 𝑹
EQUIVALENT GRAPHS
Are the graphs below equivalent?
EQUIVALENT GRAPHS
Are the graphs below equivalent?
PATH A path in a graph is a sequence of edges which joins a
sequence of distinct vertices.
𝑢1 − 𝑢5 − 𝑢2 − 𝑢3 𝑣5 − 𝑣4 − 𝑣3 − 𝑣1 − 𝑣2
CIRCUIT A circuit is a closed path/cycle where a path ends at the same
vertex at which it started.
𝒖𝟏 − 𝑢5 − 𝑢2 − 𝑢3 − 𝑢4 − 𝒖𝟏
𝒗𝟏 − 𝑣2 − 𝑣3 − 𝑣4 − 𝑣5 − 𝒗𝟏
EULER PATH EULER CIRCUIT
It is a path where each edge in a graph It is a circuit/cycle where each edge in a
is traversed once and starts and ends graph is traversed once and starts and
at a different vertex. ends at the same vertex.
𝟏−2−3−4−5−1−𝟒 𝟏−2−3−4−5−𝟏
Find an Euler circuit in the figure below: (Page 232, Figure 6.5)
A-B-C-E-H-G-F-D-G-E-B-D-A
DEGREE It refers to the number of edges that is incident
OF A VERTEX at a vertex.
𝑨 This means that the degree of a vertex indicates the
number edges connected to that vertex.
𝑑𝑒𝑔 𝐴 = 2
𝑬 𝑩
𝑑𝑒𝑔 𝐵 = 4
𝑑𝑒𝑔 𝐶 = 3
𝑑𝑒𝑔 𝐷 = 3
𝑫 𝑪 𝑑𝑒𝑔 𝐸 = 4
EULERIAN GRAPH THEOREM
Eulerian Graph Theorem
A connected graph is Eulerian if and only if every vertex of the graph is of even
degree. Furthermore, the graph is Eulerian if it has an Euler circuit.
Which of the following graphs is Eulerian? (Page 233, Example 3)
APPLICATION OF EULERIAN GRAPH THEOREM
(Page 234, Example 5)
Is it possible to plan a
journey that traverse the
tracks and returns to the
starting point without
traveling through any
portion of a track more
than once?
EULER PATH THEOREM
Euler Path Theorem
A connected graph contains an Euler path if and only if the graph has two
vertices of odd degree with all other vertices of even degree.
Which of the following has an Euler path? (Page 233, Example 3)
recall… The Konigsberg Problem
Can you walk through each bridge exactly once?
THE KONIGSBERG PROBLEM
Can you walk through each bridge exactly once?
Historical background
Leonard Euler (1707-1783) – American mathematician
and logician introduced this formal definition of relation
APPLICATION OF EULER PATH THEOREM
(Page 236, Example 6)
Is it possible for the
photographer to design a
trip that traverses all the
roads exactly once?
APPLICATION OF EULER PATH THEOREM
(Page 236, Check your progress 6)
Is it possible for the cyclist to
traverse all of the trails
without repeating any
portions of the trip?
APPLICATION OF EULER PATH THEOREM
(Page 236,
Example 7)
APPLICATION OF EULER PATH THEOREM
𝑩 𝑪 𝑫
𝑬
𝑨 𝑭
(Solution, Page 237, Example
7)
End of Discussion…
