MATH1081 DISCRETE MATHEMATICS Term 2 2019
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Term 2 2019
MATH1081
DISCRETE MATHEMATICS
1. i) Are the following graphs isomorphic to each other? Prove your answer.
a
b e
f
c d
ii) Consider the following graph G .
x w
z
y v
u
T
V S
W R
X Q
Y P
a) Does G contain an Euler path? Give reasons.
b) Show that G is bipartite.
c) Prove that G does not contain a Hamilton circuit.
iii) Find a minimal spanning tree in the following weighted graph. Show all
your working.
B
5
3
2
4
D
iv) Show that the following graph is not planar. b c
a g d
f e
v) A spanning tree in the complete bipartite graph K2,n is a tree which is a subgraph of K2,n and includes every vertex of K2,n . In the case n = 4 , two examples are given below. Note that although these two graphs are isomorphic, they are di
erent graphs because they do not contain the same edges.
v
u1 v
u2 v
v
How many di
erent spanning trees graph K2,n ? Give detailed reasons
v
u1 v2
u2 v3
v
are there in the complete bipartite for your answer.
2. i) Solve the congruence 39x ≡ 15 (mod 87) . Give your answer as
a) a congruence to the smallest possible modulus;
b) a congruence modulo 87 .
ii) Let S = R2 , the set of all ordered pairs of real numbers. De ne a relation ∼ on S as follows:
(x1 ,y1 ) ∼ (x2 ,y2 ) if and only if there exists a positive real number 
such that x2 = 
x1 and y2 = 
y1 .
a) Prove that ∼ is an equivalence relation on S .
b) Geometrically describe the equivalence classes of this relation.
iii) A poker hand consists of ve cards dealt from a standard pack. A poker hand is called“four of a kind”if it contains four cards of the same value and one other card, for example, ♠9, ♥9, ♦9, ♣9, ♦Q .
You and one other player are each dealt a poker hand from the same pack. (So, ten cards are dealt altogether.)
a) What is the probability that your hand is“four of a kind”?
b) You pick up your hand and see that you have“four of a kind”. What is the probability that the other player also has“four of a kind”?
iv) Consider the equation
x1 + x2 + x3 + x4 + x5 = 100 ,
where x1 ,x2 ,x3 ,x4 ,x5 are to be non–negative integers.
a) How many solutions has this equation altogether?
b) How many solutions has this equation in which all of x1 ,x2 ,x3 ,x4 ,x5 are congruent to 2 modulo 3 ?
c) How many solutions has this equation in which none of x1 ,x2 ,x3 ,x4 ,x5 is congruent to 2 modulo 3 ?
3. i) Use the formula
tanA − tanB
tan(A − B) =
to prove that
tank − tan(k − 1)
tan1
Hence simplify
n
X tank tan(k − 1) .
k=1
ii) Consider the following argument.“If I buy a new car then I will have to give up eating out and seeing movies. If I have to give up eating out then I won’t give up seeing movies. Therefore, I won’t buy a new car.”
a) Express the above argument in symbolic form using logical connec- tives. Make sure you carefully de ne any notation you introduce.
b) Show that the argument is logically valid.
iii) You are given a theorem, together with the basic ideas needed to prove it. Write up a detailed proof of the theorem. Your answer must be written in complete sentences, with correct spelling and grammar. It must include a suitable introduction and conclusion; reasons for all statements made; correct logical ow and any necessary algebraic details.
Theorem. Let a,b and m be integers. If m | ab and gcd(m,a) = 1 , then m | b .
Basic ideas. If mx + ay = 1 , then mbx + aby = b , and m | LHS .
iv) Let f : A → B and g : B → C be functions, and consider the statement
“if g is one–to–one (injective) and g ◦ f is onto (surjective), then f is onto (surjective)”.
a) Prove that this statement is true.
b) Explain carefully what is wrong with the following attempt to prove the statement false.
“Let
f : Z → R where f(x) = x
g : R → R where g(x) = x3 .
Then g is one–to–one; moreover (g ◦f)(x) = g(f(x)) = g(x) and so g ◦f = g , which is onto; however f is not onto. This counterexample shows that the statement is false.”
2022-04-29