## Transcribed Text

1. For a set X, the identity function is ix : X -> X such that ix(x) = I for all x E X.
(i) Give an example of a function f { a,b} {a, b} such that f#i{a,b} and f is bijective.
[1 mark]
(ii) Give an example of a function g : {a,b,c}
{a,b,c} such that g # i{a,b,c} and gog is
bijective.
marks]
(iii) Suppose h : X X is a function such that hoh is 1-1 (injective). Prove that h is 1-1.
2 marks
(iv) Suppose h : X
X is a function such that hoh is onto (surjective). Prove that h is
onto.
[2 marks]
2.
the equivalence relation 22 on R defined by
The equivalence classes are In = {xER/n<x<n+1}. where="" n="" ez.<br="">(i) Let k E Z. Explain why, if k E In then k =n.
[2 marks]
(ii) Let = {In /neZ} Prove that I is countable.
marks
(iii) It is known that R is uncountable. Prove that In is uncountable for every n E Z.
[3 marks]
</x<n+1}.>3. Let G be an undirected graph, and G = (V,E). Recall that a subgraph of the form
{Xp-1,xp}}) is called a path between X1 and Xp in G.
and this path has length p - 1.
Now, for integer k>1, define
Ek = {{x,y} x y and there is a path of length k in G between x and y},
and let Gk = (V,Ek). Note that E1 = E and G1 = G.
Thus, for the undirected graph in Figure 1,
a
b
we have {e,b} E E1, {e, d} E E2, {e,d} E E3. etc.
C
e
( V, E)
Figure 1
(i) List the elements of V and E for Figure 1.
2 marks]
(ii) What is the length of the longest path in Figure 1?
[1 mark]
(iii) Draw all spanning trees for the graph in Figure 1.
[3 marks
(iv) Draw G2, G3, G4 and G5 for the graph in Figure 1.
[4 marks]
(v) Identify all (if any) cyclic graphs in (iv).
[1 mark]
(vi) Identify all (if any) connected graphs in (iv).
[1 mark]
(vii) Among G2, G3, G4 and G5, which (if any) are trees?
[1 mark]
(viii) In (iv), how many connected components does G4 have?
[1 mark]
(ix) For this part, consider any G (not just the one in Figure 1). Prove that G is connected
if and only if {x,y} E U Ek for every x,y E V such that X # y.
[2 marks]
(x) Determine the number of graphs (with the same V) that are isomorphic to the graph
in Figure 1.
[5 marks]
4. Let T be a rooted binary tree of height h. For h>1, we call T a strand if and only if the
following holds:
(I) there is exactly one leaf and one parent at every level l, for <e<h- -="" 1="" and<br="">(II) there are exactly two leaves at level h.
Figure 2 below illustrates three strands T1, T2 and T3.
a
a
a
b
C
b
C
b
C
d
e
e
d
d
f
g
g
f
g
T1
T2
T3
Figure 2
(i) Is T1 = T2? Is T2 = T3? Justify your answers.
[2 marks]
(ii) Prove that, for any h > 1, a strand of height h has 2h + 1 nodes.
[2 marks]
Let N(0) = 1 and, for h>1, let N(h) be the number of different strands of height h. whose
nodes are {V1, ...,U2h+1}
(iii) Prove that N(h) = 2(2h + 1)hN(h - 1) for every positive integer h.
[5 marks]
(iv) Use induction to prove that N(h) = (2h+1)! for every positive integer h.
[5 marks]
</e<h->

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction
of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice.
Unethical use is strictly forbidden.