MATH1061/MATH7861 Discrete Mathematics Semester 2, 2021
Lecture 35 – Intro to graph theory, Walks, trails and circuits.
Learning Goals
Understand the basic terminology and definitions of graph theory.
Understand the conditions required for a graph to have an Euler circuit or trail.
Student questions and comments:
The Handshake Theorem and its corollary (every graph has an even number of vertices of odd degree); Question 2 from the pre-class questions.
Clarify the difference between an Euler circuit and an Euler trail
Will we need to find Euler circuits?
If so, by what method would we do so?
MATH1061/MATH7861 Discrete Mathematics Semester 2, 2021 Lecture 35 – Intro to graph theory, Walks, trails and circuits. Final Exam revision sessions and general information
• Exam covers the entire course and consists of 12 questions, similar in format to Sem 1 2018 and Sem 1 2019 final exams.
• This is a closed book exam. The last page of the exam is a formula sheet.
• Formula sheet will be available on Blackboard soon, along with some past exams to use for revision.
• Writing time and planning time – 2 hours and 10 minutes.
• Internal students will write the exam in person, refer to your personal timetable for time and place. Remember to bring your student card, calculator (approved/labelled), pens/pencils.
If an internal student has a compelling reason why they cannot sit the exam in person, they should email and request to complete the exam online with the external students.
• External students will complete the exam online with Zoom invigilation. A pdf of the exam questions must be downloaded from the exam Blackboard test link at the start time of the exam, and a pdf file of your solutions must be uploaded using the Blackboard submission link before the due time. You are allowed 15 minutes for scanning and uploading so you must stop writing after 2 hours and 10 minutes and you must submit before 2 hours and 25 minutes after the start time, late penalties will apply. Two past exams have been set up in Blackboard in this format so that you can practice the process of downloading and uploading. If an external student needs an alternative start time due to the time zone they are in, please email or to request this.
• You must achieve at least 45% on the final examination in order to pass the course, for details see the course profile.
Revision sessions: Monday 1 November 12:00 – 1:30pm in room 7-222 and on Zoom (everything except Fun., Rel., Groups) Friday 5 November 1:00 – 2:30pm in room 7-222 and on Zoom (Functions, Relations, Groups)
MATH1061/MATH7861 Discrete Mathematics Semester 2, 2021 Lecture 35 – Intro to graph theory, Walks, trails and circuits. Graph Theory
A graph 𝐺 is a non-empty set of vertices 𝑉 𝐺 and a (possibly empty) set of edges 𝐸(𝐺), where each edge is associated with a set consisting of either one or two vertices.
Vertices: dots Edges: lines joining two dots, or joining a dot to itself
Recall that a graph is simple if it has no loops and no multiple edges.
Recall that the degree of
a vertex is the number of edge ends incident with it.
multiple edge
The Handshake Theorem says that the sum of the degrees of a graph is twice the number of edges. If 𝐺 is a graph with 𝑉 𝐺 = {𝑣 , 𝑣 , … 𝑣 } and 𝐸 𝐺 = 𝑒, then
deg𝑣𝑖 =2𝑒. 𝑖=1
MATH1061/MATH7861 Discrete Mathematics Semester 2, 2021
Lecture 35 – Intro to graph theory, Walks, trails and circuits.
Question 2 from the pre-class questions:
Option (c) is a corollary of the Handshake Theorem
deg 𝑣 =deg 𝑣 +deg 𝑣 +⋯+deg(𝑣 )=2𝑒. 𝑖12𝑛
one vertex of even degree so (a) is false.
two vertices of even degree so (b) is false.
two vertices of odd degree so (d) is false.
Challenge Activities:
1. Prove or disprove: Every connected Eulerian simple graph with an even number of vertices has an even number of edges.
2. During a meeting of 2𝑛 people, there were more than 𝑛2 handshakes. No one shook hands more times than Angelo did. Prove that amongst the participants shaking hands with Angelo there were two who shook hands with each other.
MATH1061/MATH7861 Discrete Mathematics Semester 2, 2021
Lecture 35 – Intro to graph theory, Walks, trails and circuits.
Activity 4 (from last lecture):
For each of the following lists, draw a simple graph with vertices whose degrees are the numbers in the list, or explain why no such graph exists.
(a) 2,2,2,2
(c) 4,3,2,2,2,2,1,1
(d) 1,1,1,1
(e) 5,5,5,5,5,5
The list of degrees of the vertices in a graph is called the degree sequence of the graph.
MATH1061/MATH7861 Discrete Mathematics Semester 2, 2021 Lecture 35 – Intro to graph theory, Walks, trails and circuits. Theorem: Any simple graph with at least two vertices has two vertices of the same degree.
Proof: Let 𝐺 be a simple graph, and let 𝑛 be the number of vertices in 𝐺. Since 𝐺 is simple, any vertex in 𝐺 has degree at most 𝑛 − 1, and at least 0.
However, if there is a vertex of degree 𝑛 − 1, then it is adjacent to every other vertex, and there cannot be a vertex of degree 0.
Thus, the maximum number of different vertex degrees in a simple graph with 𝑛 vertices is 𝑛 − 1.
Since the number of vertices is 𝑛, and the maximum number of different vertex degrees is only 𝑛 − 1, by the pigeonhole principle, there exist two vertices with the same degree.
MATH1061/MATH7861 Discrete Mathematics Semester 2, 2021 Lecture 35 – Intro to graph theory, Walks, trails and circuits.
Activity 1:
(a) A graph has 5 vertices with degree sequence 3, 3, 2, 2, 2. How many edges does the graph have?
(b) A graph has 6 vertices and 10 edges. If five of its vertices have degree 3, what is the degree of its other vertex?
MATH1061/MATH7861 Discrete Mathematics Semester 2, 2021 Lecture 35 – Intro to graph theory, Walks, trails and circuits. Complete Graphs: The simple graph with 𝑛 vertices and 𝑛 edges is called the complete graph of order 𝑛.
In a simple graph, there are no loops, and each pair of vertices is joined by at most one edge.
So to achieve the maximum number of edges possible in a simple graph with 𝑛 vertices, join each vertex to every other vertex.
Since there are 𝑛 pairs of vertices, the maximum number of edges is 𝑛 . 22
The family of complete graphs, 𝐾 𝑛
𝐾𝐾𝐾𝐾𝐾𝐾𝐾 1234567
MATH1061/MATH7861 Discrete Mathematics Semester 2, 2021
Walks, Trails and Circuits:
Lecture 35 – Intro to graph theory, Walks, trails and circuits.
A walk is a sequence
𝑣𝑒𝑣𝑒𝑣⋯𝑣 𝑒𝑣⋯𝑒 𝑣 𝑒𝑣
Activity 2: Determine whether the complete graph 𝐾 containsthefollowing:
(a) A walk that is not a trail. (b) A trail that is not a circuit. (c) An Euler circuit.
0 1 1 2 2 𝑖−1 𝑖 𝑖 𝑛−1 𝑛−1 𝑛 𝑛 where each 𝑣𝑖 is a vertex, and each 𝑒𝑖 is an edge with
endpoints 𝑣𝑖−1 and 𝑣𝑖.
A graph is connected if and only if there is a walk from any given vertex to any other given vertex.
A trail is a walk where 𝑒 ,𝑒 ,…,𝑒 are pairwise distinct. 12𝑛
A circuit is a trail 𝑣 𝑒 𝑣 𝑒 ⋯ 𝑣 𝑒 𝑣 where 𝑣 = 𝑣 . 0 1 1 2 𝑛−1 𝑛 𝑛 0 𝑛
An Euler circuit is a circuit that contains every edge of the graph.
Theorem: Let 𝐺 be a connected graph. Then 𝐺 has an Euler circuit if and only if every vertex of 𝐺 has even degree.
MATH1061/MATH7861 Discrete Mathematics Semester 2, 2021 Lecture 35 – Intro to graph theory, Walks, trails and circuits. An Euler circuit is a circuit that contains every edge of the graph.
An Euler trail from vertex 𝒖 to vertex 𝒗 is a trail that starts at 𝑢 and ends at 𝑣 and contains every edge of the graph.
Theorem: Let 𝐺 be a connected graph. Then 𝐺 has an Euler circuit if and only if every vertex of 𝐺 has even degree. Let 𝑢, 𝑣 ∈ 𝑉(𝐺) be distinct vertices of 𝐺. Then 𝐺 has an Euler trail from 𝑢 to 𝑣 if and only if 𝑢 and 𝑣 have odd degree and all other vertices of 𝐺 have even degree.
Note that the definition of Euler circuit and Euler trail given in the textbook are not the standard definitions. However, for connected graphs, their definitions are equivalent to the ones given in the video.
According to the standard definitions, this graph does have an Euler circuit.
The textbook says an Euler circuit is a circuit that contains every vertex and every edge of the graph, so by that definition, this graph does not have an Euler circuit.
MATH1061/MATH7861 Discrete Mathematics Semester 2, 2021 Lecture 35 – Intro to graph theory, Walks, trails and circuits. An Euler circuit is a circuit that contains every edge of the graph.
An Euler trail from vertex 𝒖 to vertex 𝒗 is a trail that starts at 𝑢 and ends at 𝑣 and contains every edge of the graph.
Theorem: Let 𝐺 be a connected graph. Then 𝐺 has an Euler circuit if and only if every vertex of 𝐺 has even degree. Let 𝑢, 𝑣 ∈ 𝑉(𝐺) be distinct vertices of 𝐺. Then 𝐺 has an Euler trail from 𝑢 to 𝑣 if and only if 𝑢 and 𝑣 have odd degree and all other vertices of 𝐺 have even degree.
Activity 3: For each of the following graphs, determine whether the graph has an Euler circuit. For those that do not contain an Euler circuit, determine whether the graph has an Euler trail.
Graph 𝐺2 Graph 𝐺3 Graph 𝐺 Graph 𝐺5 4
MATH1061/MATH7861 Discrete Mathematics Semester 2, 2021 Lecture 35 – Intro to graph theory, Walks, trails and circuits.
Theorem: Let 𝐺 be a connected graph. Then 𝐺 has an Euler circuit if and only if every vertex of 𝐺 has even degree. Let 𝑢, 𝑣 ∈ 𝑉(𝐺) be distinct vertices of 𝐺. Then 𝐺 has an Euler trail from 𝑢 to 𝑣 if and only if 𝑢 and 𝑣 have odd degree and all other vertices of 𝐺 have even degree.
degree, the graph is connected, so it has an Euler trail from 𝑎 to 𝑒.
Vertices 𝑎 and 𝑒 have odd degree, all other vertices have even 𝑖𝑐
MATH1061/MATH7861 Discrete Mathematics Semester 2, 2021
Lecture 35 – Intro to graph theory, Walks, trails and circuits.
How to tell if a graph has an Euler circuit:
Does every vertex have even degree?
Is the resulting graph connected?
Does the graph have any edges?
Delete all the isolated vertices.
There is an Euler circuit.
There is no Euler circuit.
There is no Euler circuit.
If there are exactly two vertices of odd degree, then there is no Euler circuit, but there is an Euler trail.
There is an Euler circuit.