Discrete Mathematics Assignment: Functions, Graphs, and Combinatorics

This Discrete Mathematics assignment addresses several key concepts, including functions, relations, and graph theory. The solution analyzes the properties of relations, determining whether they are reflexive, symmetric, and transitive. It explores the properties of functions (one-to-one, onto) and their implications. The assignment also delves into graph theory, examining Euclidean paths, Hamiltonian cycles, and minimum spanning trees, providing detailed explanations and calculations. Additionally, the document covers counting principles and chromatic polynomials, offering a comprehensive understanding of these topics. The document provides a detailed breakdown of each problem, ensuring a clear understanding of the concepts.

Running head: DISCREET MATHEMATICS 1

DISCREET MATHEMATICS 2
1. No, if you take relation R on a set 1. 2, 3
Where R={( 1,1 ) , ( 1,2 ) , ( 2,1 ) , ( 1,3 ) , ( 3,1 ) , ( 2,2 ) ,(2,3)}
The function is symmetric since for all x , yϵR there is( y , x)ϵR
Also, it is transitive as for all x , y , zϵA , ( x , y ) ϵR , ( y , z ) ϵRthereis (x , z)ϵR
Despite being transitive and symmetric the relation is not reflexive as for
xϵA , ( x , x ) ϵRis missingi.e. for x=3,(3,3)≠ R
2. A function f ( x ) isone to one iff an input yields a unique output
On the other hand, a function is onto iff every element of the image has a preimage
The function f: Z6→ Z6 will be one to one and onto which is the same case for
f: Z5→ Z5
A multiplicative inverse exists for the elements which are onto and one to one
3.
a
f b
c
e
d

DISCREET MATHEMATICS 3
In the question the vertices a, c, e and f all have vertices with odd degree of 3. Since a
Euclerian path graph cannot have more than 2 vertices of odd degree G have no
Euclerian path.
Adding one edge to the graph flips the parities of the vertices it connects that is odd to
even and even to odd. We will add edge between two vertices of odd degree
Adding ac gives fcdfaceabe
Then adding ef gives afeabecdfc which now have a Euclerian path
4. The vertices a, b, c, d, e, f is odd and of degree 3 and 1and g is an even vertex of 2
Since a graph with a vertex of degree one cannot have a Hamilton circuit then G have
no Hamiltonian cycle
5. A minimum spanning tree has the minimum weight than any other spanning tree of a
graph
h the total weight is 5+11+ 4=20
5 a
4
f
11 c
Edge ab ac ad ae af ag ah

DISCREET MATHEMATICS 4
weight 18 4 37 93 28 46 55
h 55 a 18
46 b
g 28 93 37 4 c
f e d
The total weight is 281
6. DISCRETEMATHEMATICS have 19 letters
The letters I, S, C, M, A are repeated twice while E and T are repeated thrice therefore
The total number of physical arrangements are
19 !
2!∗2 !∗2!∗3 !∗2 !∗3!∗2 !=105,594,705216000
7. Exactly 11 0’s and 9 1’s
For the case of 1’s consecutive we have 12 possibilities
For the case with all 0’s consecutive we have 10mpossibilities
Because two options are counted twice the total possibilities will be
10+12−2=20
8.
a) 52 ∁ 7= 52 !
7 !∗45 !=133784560

DISCREET MATHEMATICS 5
b) A suit contains 4 cards hence it’s not possible to select 7 cards from the same
suit, the answer is therefore 0
c) 3 aces 4 ∁ 3= 4 !
3 !∗1!=4
3 kings 4 ∁ 3=4
1 card not a king nor an ace
52−8=44
44 ∁ 1= 441
1!∗43 ! =44
¿ 44∗16=704
d) Suit have 13
13 ∁ 6∗4= 13!
6 !∗13!∗4=1716
e) 13 ∁ 1∗4= 13 !
1 !∗12!∗4=52
9.
a) The chromatic polynomial concept enables determination of the colours which are
supposed to be situated at each joint.
b) 7 ∁ 1∗3= 7 !
6 !∗1 !∗3=21
c) 7 ∁ 1∗4= 7 !
6 !∗1 !∗4=28
d) 7 ∁ 3+7 ∁ 4=35+ 35=70

DISCREET MATHEMATICS 6
(Jongsma, 2016)
References
Jongsma, C. (2016). Discrete Mathematics: Chapter 6, Functions & Equivalence Relations.
Faculty Work: Comprehensive List Paper 428.