T HE U NIVERSITY OF S YDNEY
S CHOOL OF M ATHEMATICS AND S TATISTICS
Graph Theory and Relations – Week 09 Tutorials
Math1064 Semester 2, 2025
Note: There are extra questions this week because we missed a tutorial in Week 8. Decide
as a group which questions you will complete - you do not need to go in order.
1. Let G, H and K be the graphs below.
v1 v2 v1 v2 v1
v2
v5
v3 v4 v3 v4 v3 v5
G v5 H K
(a) Which of these are simple graphs?
(b) Which of these have an Eulerian circuit?
Give a brief explanation for each of your answers.
2. For each of the following, state whether or not there exists a simple graph with vertices
having the given degrees. If your answer is “yes”, then draw such a graph. If your
answer is “no”, then explain why no such graph exists.
(a) Five vertices with degrees 3, 3, 2, 2, 2.
(b) Seven vertices with degrees 4, 2, 3, 1, 1, 1, 1.
(c) Five vertices with degrees 5, 4, 3, 1, 1.
3. Consider the following relations on the set {1, 2, 3, 4}.
• R1 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 1), (4, 4)}
• R2 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (4, 4)}
• R3 = {(1, 1), (1, 2), (1, 4), (2, 1), (2, 2), (3, 3), (4, 1), (4, 4)}
• R4 = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)}
• R5 = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)}
• R6 = {(1, 1), (2, 2), (3, 3), (4, 4)}.
For each of the relations R1 , R2 , R3 , R4 , R5 and R6 , determine whether it is reflex-
ive, symmetric, or transitive. If it is an equivalence relation, determine the equivalence
classes.
You may find it helpful to draw arrow diagrams: draw four points labelled 1, 2, 3, 4, and
draw an arrow from x to y whenever x R y.
Copyright © 2025 The University of Sydney 1
4. Define the relation R on N × N as follows: for all (a, b) ∈ N × N and all (c, d) ∈ N × N,
(a, b) R (c, d) if and only if a + d = c + b .
(a) Give three distinct elements of R.
(b) Is R reflexive?
(c) Is R symmetric?
(d) Is R transitive?
(e) If R is an equivalence relation, determine a representative for each equivalence
class.
5. Let R be the relation on Z defined by x R y if and only if x2 − y2 ≡ 0 (mod 2).
Show that R is an equivalence relation.
6. Let R be the relation on Z defined by x R y if and only if x3 − 1 < y3 .
(a) Is R reflexive?
(b) Is R symmetric or antisymmetric?
(c) Is R transitive?
(d) For any two integers x and y, show that we either have xRy or yRx.
7. Let X be a set with exactly seven elements. How many equivalence relations with pre-
cisely four equivalence classes are there on X?
8. For each n ∈ N, the complete graph Kn is the simple graph with n vertices and an edge
between every pair of vertices.
(a) Draw K3 , K4 , K5 and K6 .
(b) What is the degree of each vertex in Kn ?
(c) For which n does Kn contain an Eulerian circuit?
9. Consider the graph G from Question 1.
(a) Write down the adjacency matrix A of this graph.
(b) Compute the matrices A2 and A3 .
(c) In G, how many walks are there of length 3 from v2 to v5 ?
10. Let G be a simple graph with at least two vertices. Show that G has two vertices of the
same degree.
11. Prove that if v is a vertex of odd degree in a graph G, then there is a path in G from v to
another vertex of odd degree.
