DMTH137 Assignment 2: Problem Set on Graphs, Functions, & Counting

This document provides solutions to DMTH137 Assignment 2, focusing on topics related to graphs, functions, and counting. The assignment covers determining graph planarity, applying Kruskal's algorithm to find maximal weight spanning trees, analyzing one-to-one functions and their ranges, using the binomial theorem to find coefficients, and applying set theory principles to solve counting problems. Specific questions address planar graph identification, maximal spanning tree construction, function invertibility, coefficient determination in binomial expansions, and integer counting based on set intersections and unions. The solutions provide step-by-step explanations and calculations, referencing relevant theorems and algorithms.

Q1.
a) A planar graph can be drawn without the edges crossing each other.
b) A graph is not planar if it can be drawn with the edges crossing each other.

Q2.
We use Kruskal’s algorithm to find maximal weight spanning tree. We start by an empty graph
and then we draw an edge with maximum weight and ensure a cycle is not created. We then
remove any edge added to the maximal spanning tree on the original graph or one that has been
discarded at current time. Proceed to the next time step. Continue until you obtain a spanning
tree.
Q3
a) f ( x ) = 2 x−3
4 x−5
i) Show that f is one-to-one
For the function to be one-to-one, f ( x1 ) =f ( x2 ) ⇒ x1 =x2
Taking x1 ⇒ R and x2 ⇒ R, f ( 1 ) = 2 ( x1 ) −3
4 ( x1 )−5 ≠ 2 ( x2 )−3
4 ( x2 ) −5
Therefore, f is not one-to-one.

ii) Range of the f
y= 2 x−3
4 x−5
Interchanging the variables;
x= 2 y−3
4 y−5
Solving for y;
y= (−3+5 x )
2 (−1+2 x )
¿ −3+5 x
2(−1+2 x )
Finding the domain of each inverse function;
Domain of −3+5 x
2(−1+2 x ): x < 1
2 ∨x > 1
2
Substituting x= 1
2in the function to obtain singularity point and equate it to 0 we
get x= 1
2
The function domain x > 1
2 ∨x < 1
2
Combining the ranges;
f ( x ) > 1
2 ∨f ( x ) <1
2
iii) From (ii) we obtained y= −3+ 5 x
2(−1+2 x) which brings x= 5 y−3
4 y−2
This leads to a g ( y )= 5 y−3
4 y−2
Therefore, g ( f ( x ) )=
5 ( 2 x−3
4 x−5 )−3
4 ( 2 x−3
4 x−5 )−2
=x

Similarly, f(g(y)) ¿
2 ( 5 y−3
4 y−2 )−3
4 ( 5 y−3
4 y−2 )−5
= y
Hence f is invertible and f −1=g which is given by f−1 (x)= 5 x−3
4 x−2
b) f ( 10 , 4 )= {{ 4 if b=a
f ( 6 , 4 ) if a>b
c) f ( x )=5 x +2∧g ( x )=9 x +c
fog=5 ( 9 x+c ) +2=45 x +2+5 c
gof =9 ( 5 x +2 ) +c=45 x +18+ c
Equating the two;
45 x +2+5 c=45 x +18+c
Making c the subject
c ( 5−1 ) =45 x−45 x +18−2
c=4
Q4
Coefficient of x14.
( 3−2 x2 )10
From binomial theorem (Douglas Smith, 2014);
( x + y )n=xn +C1 xn−1 y +C2 xn−2 y2 +… … … … …
To obtain a power 14, we find the seventh term;

7th term: 10 !
7 ! ( 10−7 ) ! ∗33 ( −2 x2 )
7
=−414720 x14
The coefficient is -414720
Q5
a) Range g ( y ) =k−z199. Since it contains f which has range containing at least 100 elements,
g( y ) also contains at least 100 elements.
b) An element belonging to f does not belong to g. This clearly shows that they are not
disjoint (Kubrusly, 2013).
c) g ( y ) +f ( y ) =k
g( y ) is a function of f ( x) which means we can express g( y ) in terms of f (x)
That is, f ( x ) + f ( y )=k
Q6.
a) Let P, Q, R, and S be the required integers We want ¿ ( P ∪Q∪ R ∪S ∪T ) c∨¿
|P|=1000
2 =500 ;|Q|= 1000
3 333 ;|R|=1000
5 =200 ;|S|= 1000
7 =142;
|P ∩Q|=1000
6 166 ;|P ∩ R|= 1000
10 =100 ; P ∩ S=1000
14 =71 ;Q ∩ R= 1000
15 66 ;
Q ∩S= 1000
21 =47 ; R ∩ S=1000
35 =28; P ∩QR= 1000
30 =33 ; P∩Q ∩ S=1000
42 =23
P ∩ R ∩S= 1000
70 =14 ; Q ∩ R ∩S= 1000
105 =9 ; P∩ Q∩ R ∩ S=1000
210 =4
|( P ∪ Q∪ R ∪ S ∪ T )❑
|=500+333+200+142−166−100−71−66−47−28+33+ 23+14+9=772
Number of integers required = 1000-772 = 228.

b) 10000=24∗54
φ ( 64000 )=64000 Π (1− 1
p )=25600
Q7
The solution will be 5C17 = 17 !
( 17−5 ) !∗5 ! =6188
Q8

Bibliography
o la mit M A A Tran ition to Ad anced Mat ematic n l en a e earninD ug s S h, . E. R. S. ., 2014. s v h s. I : s. .:C g g L g.
r l lement o perator T eor n l prin er cience ine MediaKub us y, C. S., 2013. E s f O h y. I : s. .:S g S & Bus ss .