The University of Sydney School of Mathematics and Statistics
Assignment 2
MATH2069: Discrete Mathematics and Graph Theory Semester 1, 2021
This assignment is worth 5% of the assessment for MATH2069. It is based on material covered in Graph Theory lectures and is due before 11:59pm on Friday 21 May. Please upload your assignment as a single PDF file to Canvas. Poorly scanned or other- wise difficult to read assignments may not be marked.
To guard against unconscious bias we ask that you do not put your name on your as- signment. Instead please write your student number on the first page of your assignment. To be awarded full marks, all answers must be accompanied with complete arguments.
1.
2.
3.
Determine and explain whether or not the following graph is Hamiltonian:
(a) Find the number of the isomorphism classes of connected graphs with 5 vertices and 5 edges. Draw a graph representing each class.
(b) Use your solution of part (a) to find the number of the isomorphism classes of graphs with 5 vertices and 6 edges which have
(i) an Eulerian circuit;
(ii) an Eulerian trail.
Consider the trees with the vertex set {1, 2, 3, 4, 5, 6}.
(a) Write down all possible degree sequences of these trees.
(b) Prove or disprove the following claim: If (a, b, c, d) is the Pru ̈fer sequence of a tree T , then any permutation of this sequence corresponds to a certain tree T′ isomorphic to T.
Copyright ⃝c 2021 The University of Sydney