Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Mathematical Sciences

Summer 2021

M210 Discrete Mathematics

Assignment for Week 5

#1 (2 marks) You are dealt 7 cards from a standard 52 card deck. In how many ways can you receive 3 pairs and a singleton?

#2 (1+1+1+1=4 marks) A judging panel is to consist of three judges. There are two judges from the Solomon Islands, three judges from Fiji, five judges from New Zealand and seven judges from Australia. Determine the number of ways of forming a panel under the following restrictions.

(a) There must be one judge from each of the Solomon Islands, Fiji, and New Zealand.

(b) There must be at least one judge from Fiji or the Solomon Islands.

(c) The panel must be multi-national.

(d) There must not be any Australians or New Zealanders on the panel.

#3 (1+1+1=3 marks) For each of the following degree sequences, prove that a simple graph with 8 vertices exists or does not exist by either drawing such a graph or showing mathematically that such a graph is impossible.

(a) 1,1,2,3,4,5,6,7.

(b) 1,2,2,3,3,4,6,7.

(c) 1,2,2,2,4,4,6,7.

#4 (2+2=4 marks) A simple graph G has 10 vertices and 38 edges.

(a) Prove that G does not have an Euler circuit.

(b) Prove that G must have a Hamilton circuit. (Hint: You will need Ore’s Theorem.)

#5 (2 marks) A simple graph with n ≥ 2 vertices satisfies the following property:

For any two distinct vertices u, v, Deg(u)+Deg(v) ≥ n − 1.

Prove there is a path of length at most 2 between any two vertices.

#6 (5 marks) Each edge of K6 is randomly coloured either black or white. Prove that there must be a monochromatic triangle (a triangle, all of whose edges have the same colour). (Hint: Start by considering a single vertex and use pigeonhole principle on the edges incident with it.)