MAS2707
Semester 2
Groups and Algorithms
2022/2023
Homework Assignment 3
Please submit all questions from this sheet as your third assessed piece of coursework by
Friday, March 24, 4pm.
Easy problems.
1. Consider the following graphs (some of them multigraphs, some of them directed graphs,
some with loops). Which ones are Eulerian, and which ones are semi-Eulerian? Find an
Eulerian circuit if you can; otherwise find an Eulerian path if you can, and if you can’t
find either explain why it does not exist.
(a) Γ1 = K4.
(b) Γ2 = K2,2.
(c) Γ3 with vertices {a, b, c, d, e} and the adjacency matrix
A(Γ3) =
a b c d e

1 1 1 1 1 a
1 1 0 0 1 b
1 0 1 0 1 c
1 0 0 1 1 d
1 1 1 1 1 e
(d) Γ4 with vertices {A,B,C,D,E, F} and the adjacency matrix
A(Γ4) =
A B C D E F

0 1 1 0 0 0 A
0 0 1 0 0 0 B
0 0 0 1 1 0 C
0 0 0 0 1 0 D
1 0 0 0 0 1 E
1 0 0 0 0 0 F
(e) Γ5 with vertices {α, β, γ, δ} and the adjacency matrix
A(Γ5) =
α β γ δ

0 2 1 1 α
2 0 1 1 β
1 1 0 1 γ
1 1 1 0 δ
Medium problems.
2. Let G be a group of order 85. Show that G contains an element of order 5.
3. For the graphs in Q1, calculate the number of paths of length 4 between the following
vertices:
(a) For Γ3, between a and b.
(b) For Γ4, between A and B.
Hard problems. (Will be marked for feedback only, these marks does not count
towards your final mark.)
4. Do exercise 48 from the notes - find the number of paths of length n in K3,3.
5. Do the same for K2,3, or if you can, Kr,s.
6. How does Euler’s theorem extend to directed graphs?