MATH2302/7308 Assignment 3
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
MATH2302/7308
Assignment 3
2022
This Assignment is compulsory, and contributes 10% towards your final grade in MATH2302 or MATH7308. It should be submitted by 2pm on Monday 10 October, 2022. In the absence of a valid excuse, assignments submitted after the due date will not be marked. (See the ECP for how to request an extension.) You should submit your assignment electronically.
Prepare your assignment as a PDF file, either by typing it or by scanning your handwritten work. Ensure that your name, student number and tutorial group number appear on the first page of your submission. Check that your PDF file is legible and that the file size is not excessive. Files that are poorly scanned and/or illegible may not be marked. Upload your submission using the assignment submission link in Blackboard.
The last question has two versions. One is for MATH2302, the other is for MATH7308. Submit only the one corresponding to your course code!
1. (10 marks) Consider the word abcb − 1 deca − 1 ed − 1 .
(a) (1 mark) Draw the polygon that this word represents.
(b) (2 marks) Calculate the Euler characteristic of the corresponding surface.
(c) (1 mark) Calculate the orientability of the corresponding surface.
(d) (4 marks) Use the word rules to convert this word into a connected sum of tori and/or projective planes.
(e) (2 marks) Using any of the results above, identify the surface the word represents, in terms
of the Classification Theorem.
2. (3 marks) Draw a map on the Klein bottle with six regions, each pair of which are adjacent to each other. (This proves that the chromatic number of the Klein bottle is > 6.) You may use colours or labels to indicate regions.
3. (4 marks total) Which of the following degree sequences are graphical? Justify your answer.
(a) (1 mark) 6, 5, 5, 2, 1, 1
(b) (1 mark) 8, 3, 3, 3, 2, 2, 2, 1, 1, 1
(c) (1 mark) 7, 5, 5, 3, 2, 1, 1, 1, 1
(d) (1 mark) 8, 5, 5, 4, 3, 3, 3, 2, 1, 1
4. (3 marks) Draw two non-isomorphic graphs with degree sequence 3, 3, 2, 2, 2, 2, such that exactly one of the graphs has a bridge. Label all cut-vertices and bridges.
5. (3 marks total)
(a) (1 marks) Let F be a forest graph of order p with k components. Calculate the number of
edges in F , in terms of p and k .
(b) (2 marks) Let G and H be two graphs of the same order and size. Prove that if H contains
more components than G, then H must contain at least one cycle.
6. (12 marks total) Recall that Qn is the hypercube, for any integer n > 1. The vertex set consists of all binary strings of length n, and vertices are adjacent if and only if the binary strings differ in exactly one place. Let qn,0 be the string of n zeros, and let qn,1 be the string of n ones. Define Rn to be Qn with the addition of one vertex a, and two edges connecting a to qn,0 and qn,1 .
(a) (2 marks) For which n > 1 is Rn Eulerian? For which n > 1 is Rn semi-Eulerian? Justify
your answer.
(b) (4 marks) For which n is Rn(C) Hamiltonian? Justify your answer.
(c) (4 marks) Prove that Rn is bipartite if and only if n is even.
(d) (2 marks) Prove that if n is even, then Rn is non-Hamiltonian (part (c) may be useful).
7. (5 marks) MATH2302 version A biologist images a slide at two different times. In each case six cells were identified, and the xy coordinates calculated.
On image 1, the cells were labelled a, b, c, d, e, f, with the following coordinates in microns: (7.1, 3.4), (5.6, 3.9), (4.9, 2.3), (3.1, 5), (2.2, 3.7), (3.9, 1.1).
On image 2, the cells were labelled r, s, t, u, v, w, with the following coordinates in microns: (5.9, 2.5), (6.1, 4.4), (3.7, 5.7), (2, 4.8), (2.9, 3.5), (3.8, 1.8).
The biologist wants to match up the cells between the two image to measure movement, but believes that the maximum possible cell displacement between the images is 2 microns. Use Hall’s Theorem to show that it is impossible to match all the cells in the two images so that the distance between matched pairs is always less than 2 microns.
7. (5 marks) MATH7308 version A plant breeder wishes to cross two crop varieties A and B to create a new hybrid. Seven families are available from each variety, and these need to be crossed in pairs (so each family is used in exactly one pairing, and each pairing takes one familiy from each variety). Genetic testing has been carried out, and each family has a score between 1 and
100 on two aggregate genetic scores. The labels and scores are as follows:
Variety 1, labelled a1 , . . . , a7 : (92, 82), (27, 85), (94, 35), (71, 11), (80, 23), (50, 69), (40, 82) Variety 2, labelled b1 , . . . , b7 : (45, 76), (25, 63), (63, 21), (10, 86), (50, 66), (79, 7), (69, 8)
The breeder wishes to maximise genetic diversity by ensuring that for each cross, both of the genetic scores differ by at least 20. Use Hall’s Theorem to prove that this is not possible.
2022-09-28