Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
MAST30011 Graph Theory
Assignment 1
Student Name Student Number
Tutor’s Name Practical Class Day/Time
Submit your assignment online in Canvas LMS.
Please attach this cover sheet to your assignment or use a blank sheet of
paper as the first page of your assignment with Student Name, Student
Number, Tutor’s Name, Practical Class Day/Time clearly stated.
• Late submission will not be accepted unless accompanied by a medical certificate
(or a similar special consideration). If there are extenuating circumstances you
need to contact your lecturer, preferably prior to the submission deadline. Medical
certificates are usually required.
• Information on how to submit assignments can be found in the Canvas LMS.
• Full working must be shown in your solutions.
• Marks will be deducted for incomplete working, insufficient justification or incorrect
use of terminology.
• There are 6 questions (on two pages) worth 40 marks in total.
• This assignment will contribute 10% to your final mark.
MAST30011 Graph Theory 2022
ASSIGNMENT 1
Due 13:00pm Thursday 14 April 2022
1. In the following graph, [8 marks]
(a) give an example of a longest trail
(b) give an example of a longest cycle
(c) give an example of a longest path
(d) list all induced subgraphs which are paths of length 4
(e) list all bridges of the graph
(f) compute the eccentricities of a, b, c, d, respectively
(g) give the diameter of the graph
(h) give an automorphism of the graph which is not the identity map from the
vertex set to itself.
w
a
b
c
d
u
v
Figure 1: Question 1
2. Let T be a tree with order n ≥ 8 in which every non-leaf vertex has degree 7. Prove
that n ≡ 2 mod 6 (that is, there exists an integer k such that n = 6k + 2). Prove
further that the number of leaves of T is strictly greater than 5n
6
. [6 marks]
3. Prove that a nontrivial graph is a tree if and only if it has exactly one spanning
tree. [6 marks]
4. Let G be the following weighted graph, where the number next to each edge is the
weight of the edge.
Apply Dijkstra’s algorithm to find the distance from a to all other vertices of G.
State what the labels of vertices are when each new vertex is chosen to be added
to the set S. Draw the tree of shortest paths obtained from your implementation
of the algorithm, and explicitly give the shortest path from a to every other vertex
obtained from this tree. [6 marks]