Description

connected-argument
CS/MATH 113 Discrete Mathematics
Functions
1. 5 points Consider these functions from the set of students in a discrete mathematics class. Under what conditions is the function one-to-one if it assigns to every student,
a) their mobile phone number.
Solution: This function will normally be one to one as each student will have a different unique mobile phone number, unless two students use or have the same phone number for some reason.
b) their student identification number.
c) their final grade in the class.
Solution: This will not be one to one function as two or more students can have the same grade. So unless the number of students is less than or equal to the total possible grades, this will not be one to one.
d) their home town.
Solution: This function will usually not be one to one as it is very likely that two or more students in the same class will be from the same hometown. So unless each student is from a different hometown, this will not be one to one.
e) their Ehsas hour appointment.
Solution: This function will be one to one function as each student will be given a different time for appointment, unless group appointments are allowed in which case it will no longer be one to one.
2. 5 points If f and f ◦ g are one-to-one, does it follow that g is one-to-one? Justify your answer.
1
Solution:
Let f be a function from C to D, and and f ◦ g be the composition of functions f and g, such that g is a function from A to B, then the range of f is a subset of the domain of f. We know that f and f ◦ g are one-to-one, which means for all a,b in C, f(a) = f(b) if and only if a = b, and for all c,d in A, f ◦ g(c) = f ◦ g(d) if and only if c = d
Proof by contradiction:
Suppose g is not one-to-one, i.e, at least two elements in A map to at least one element in B. This means that at least one element in the domain of f has at least two preimages in the range of g. By the definition of composition, for f ◦ g, the preimage of some element in the range of g is also the preimage of some element in the range of f ◦ g, now since g is not one-to-one, at least one element in f ◦ g must have two preimages in the domain of g. However, we know that f ◦ g is one-to-one. There arises a contradiction and our supposition must be wrong. Hence, g must also be one-to-one.
Direct proof:
g(a) = g(b) → a = b
Let, g(a) = g(b)
Applying function f f(g(a)) = f(g(b)) f ◦ g(a) = f ◦ g(b)
Since f ◦ g is one-to-one,
a = b hence proven.
3. 5 points Prove that a strictly decreasing function from R to itself is one-to-one. Give an example of a decreasing function from R to itself that is not one-to-one.
Solution: For strictly decreasing, f(x) = f(y) if and only if x = y. Contrapositively, if x ̸= y, then f(x) ̸= f(y). So then either x < y or x > y. If x < y, then f(x) > f(y) by the definition of strictly decreasing function. Similarly if x > y, then f(x) < f(y) by the definition of strictly decreasing function. Therefore f(x) ̸= f(y) when x ̸= y. So for f(x) = f(y) to be true, x must be equal to y. Therefore a strictly decreasing function from R to itself must be one to one.
An example of a decreasing function that is not one to one can be f(x) = −|x| as for x > y, f(x) ≤ f(y).
Graphs
(a) 5 points Use a bipartite graph to model the four architects and the courtyards that they can design.
Solution:

Solution:
Hall’s marriage theorem states,
The bipartite graph G = (V,E) with bipartition (V1, V2) has a complete matching from V1 to V2 if and only if |N(A)| is greater than or equals to —A— for all subsets A of V1.
Here, there will be 16 subsets of V1 (architects). Following are the subsets of architects along woth thier cardinality and the cardinality of their neighborhood:
Parveen Prime (1) = 3
Queen Quratulain (1) = 2
Reena Rani (1) = 2
Super Sonam (1) = 2
Parveen Prime, Queen Quratulain (2) = 4
Parveen Prime, Reena Rani (2) = 3
Parveen Prime, Super Sonam (2) = 4
Queen Quratulain, Reena Rani (2) = 3
Queen Quratulain, Super Sonam (2) = 3
Reena Rani, Super Sonam (2) = 4
Parveen Prime, Queen Quratulain, Reena Rani (3) = 4
Parveen Prime, Queen Quratulain, Super Sonam (3) = 4
Parveen Prime, Reena Rani, Super Sonam (3) = 4
Queen Quratulain, Reena Rani, Super Sonam (3) = 4
Parveen Prime, Queen Quratulain, Reena Rani, Super Sonam (4) = 4
Hence, Hall’s marriage theorem is passed and there can be a complete matching from architects to courtyards.
Solution: Parveen Prime −− > Darkness
Queen Quratulain −− > Ice Reena Rani −− > Light
Super Sonam −− > Nature
5. The simple graphs G1 = (V1,E1) and G2 = (V2,E2) are isomorphic if there exists a one-to-one and onto function f from V1 to V2 with the property that a and b are adjacent in G1 if and only if f(a) and f(b) are adjacent in G2, for all a and b in V1. Such a function f is called an isomorphism. Two simple graphs that are not isomorphic are called non-isomorphic.
In other words, when two simple graphs are isomorphic, there is a one-to-one correspondence between the vertices of the two graphs that preserves the adjacency relationship. Isomorphism of simple graphs is an equivalence relation.
Determine which of the following pairs of graphs are isomorphic. For each pair of graphs, provide an isomorphism (a bijection between the vertices of the graphs) or a rigorous argument that no such bijection exists.
a1 b1 c1 d1 a2b2d2
a5b5 c2c4d5
a3b3d3
a4 b4 c3 d4
Graph A Graph B Graph C Graph D
(a) 5 points Graph A and Graph B
Solution: Yes this pair is isomorphic. A possibility can be f(a1) = b1, f(a2) = b3, f(a5) = b4, f(a3) = b5, f(a4) = b2.
(b) 5 points Graph A and Graph C
Solution: This pair is not isomorphic as in Graph C, the maximum degree is 3 which is not true for Graph A that has degree 2.
(c) 5 points Graph A and Graph D
Solution: This pair is not isomorphic as in Graph D, the maximum degree is 4 which is not true for Graph B that has degree 2.
(d) 5 points Graph B and Graph C
Solution: This pair is not isomorphic as in Graph C, the maximum degree is 3 which is not true for Graph B that has degree 2.
(e) 5 points Graph B and Graph D
Solution: This pair is not isomorphic as in Graph D, the maximum degree is 4 which is not true for Graph B that has degree 2.
(f) 5 points Graph C and Graph D
Solution: This pair is not isomorphic as in Graph D, the maxmium degree is 4 which is not true for Graph C that has degree 3.
6. 5 points Show that in a simple graph with at least two vertices there must be two vertices that have the same degree.
Solution:
A simple graph is an undirected graph with only one edge between two distinct vertices and has no loops.
Proof by contradiction:
Suppose that in a graph with at least two vertcies, there does not exist any two vertices with the same degree.
Since it is a simple graph, the possible amount of degrees the graph can have is D = {0,1,…,n−1}. For none of the vertices to have the same degree, every vertex should have a distinct degree from the n possibilities in D. However, if there is a one-to-one correspondence between the the set of all vertices V and the possibilities of degrees D, then there arisesa contradiction. If one vertex has a degree of, then another vertex cannot have degree of n-1 simultaneously. This means that there cannot exist a one-to-one correspondence, and at least two vertices have to have the same degree for it to be a simple graph.

7. 5 points The complementary graph G of a simple graph G has the same vertices as G. Two vertices

are adjacent in G if and only if they are not adjacent in G. Given G with v vertices and e edges, how

many edges are there in G? Justify your answer.

Solution: G has all vertices in G but all edges that do not exist in G. Thus the number of edges

in G can be found by subtracting the number of edges e in G from total possible edges that can be made in the graph G. For v vertices in a simple graph G, each vertex can have v −1 possible edges. So total possible edges for v vertices become v number of edges times total possible edges for each vertex which is v(v − 1). However, this means that each edge will have been counted twice, thus the total possible edges will be divided by 2 to compensate the doubled counting. Then the total
number of possible edges become . A simple graph G has e edges and its complement G will
have those edges that do not exist in G. So G will have the remaining edges that are number of edges where v is the number of vertices and e is the number of edges in a simple graph G.
Induction
8. Prove the following using induction.
(a) 5 points Given a a relation R that is reflexive and transitive, Rn = R for all positive integers n.
Solution: (Proof by mathematical induction)
Base Case: For n = 1, R1 = R which is trivially true.
Inductive Hypothesis: Suppose that Rn = R is true. (This is the inductive hypothesis) Inductive Step: Rn+1 = R. By definition of composite relations, Rn+1 = Rn ◦ R. Then, Rn ◦ R ⊆ R and R ⊆ Rn ◦ R.
Transitive: For (a,c) ∈ Rn◦R, there must be an element b such that (a,b) ∈ R and (b,c) ∈ Rn. Then by the inductive hypothesis, (b,c) ∈ R and (a,b) ∈ Rn. Since R is transitive, (a,c) ∈ R. Since (a,c) ∈ Rn ◦ R, therefore proved that R ⊆ Rn ◦ R and Rn ◦ R ⊆ R. Hence Rn = R.
Reflexive: ∀a ∈ A, (a,a) ∈ R and (a,a) ∈ Rn by the inductive hypothesis. Then by definition of composite relations, (a,a) ∈ Rn ◦ R. Therefore, Rn ◦ R ⊆ R and R ⊆ Rn ◦ R. Thus proved that Rn = R.
(b) 5 points A relation R on a set A is transitive if and only if Rn ⊆ R for all positive integers n.
Solution: IF: Suppose that Rn ⊆ R for all positive integers n. Then for the base case, R2 ⊆ R. If (a,b) ∈ R and (b,c) ∈ R, then by definition of composition, (a,c) ∈ R2. Since R2 ⊆ R, then (a,c) ∈ R. Therefore, R is transitive.
Only IF:

(Proof by mathematical induction)
Base case: For n = 1, R1 ⊆ R, which is trivially true.
Inductive Hypothesis: Suppose Rn ⊆ R is true. (This is the inductive hypothesis)
Inductive Step: For n + 1, Rn+1 ⊆ R. By definition of composition, Rn+1 = Rn ◦ R. Assume that (a,c) ∈ Rn+1. Then because Rn+1 = Rn ◦ R, there exists an element b such that (a,b) ∈ R and (b,c) ∈ Rn. Then the inductive hypothesis implies that (b,c) ∈ R. Moreover, since R is transitive, and (a,b) ∈ R, and (b,c) ∈ R, then (a,c) ∈ R as well. Since (a,c) ∈ R and (a,c) ∈ Rn+1, this shows that Rn+1 ⊆ R.
Hence proved.
9. 5 points Prove via induction that a complete graph with n vertices contains edges.
Solution: Let
Base Case (n = 1): = 0. This is true as a complete graph with 1 vertex will have 0 edges.
Inductive Hypothesis (n = k): Suppose that our statement is true for n = k. Then S(k) =
edges.
Inductive Step (n = k + 1): Then for n = k+1, there should be
edges.
S(k +1) has S(k) edges + total edges by adding one more vertex. In a complete graph, each vertex is connected to all other vertices, therefore adding 1 vertex introduces k edges where k is the number of existing nodes in the graph. k edges are added on adding one node as that node is then connected to k other nodes, thus k edges are added. Then S(k + 1) = S(k) + k.
Therefore we arrive at the same conclusion that was needed, and thus the statement has been proved by induction.