1) A and B being a finite set with A > B and f : A > B f being a linear mapping. Show that f is not
injective
2) π β β
 being a positive natural Number. A and B being a finite set with A > k B and f : A > B f
being a linear mapping. Prove that there is a π β π΅ with π
β1
({π}) β₯ π +1
π
β1
: P(B) > P(A) being the inverse image of f.
3) A being a non empty, finite set. An image f called 2Colouring of a, if you assign a colour to every
element from A. Show through complete induction that there are 2
π΄
variations of 2Colouring from
A.
4) A Word with the length π β β from the Alphabet β := {0, 1} is a
Squence w = (π€0
, π€1
, β¦ , π€πβ1) β β
π
. In the case π =0 itβs the empty word/sequence(). π β β .
Prove that there are 2
π+1 β 1 Words with a length of maximum n over the Alphabet β
5) π β β, A a finite set with A=n and β := {0, 1}. F being the amount of all 2Colouring from A, and W
the amount of all Words of the length π over the Alphabet β.
Show that there is a Bijection between F and W.
6) G is a connected graph and π β β is chosen that for all blocks π΅ β G applies π(π΅) β€ π.
a) State an algorithm (without reasoning) that provides a largest (concerning Cardinality)
independent set in G and itβs runtime is in π(π(π)π(π(πΊ))).
f being a function described by f: β β β that only depends on k while p: β β β is a
polynomial that only depends on π(πΊ).
b) Prove the correctness of the algorithm from a
c) Justify why the runtime from a is in π(π(π)π(π(πΊ))).
7) π β β  a positive natural number. We know one Graph G, that is able to be made cplanar, that if
there is a set π β V(G) with maximum of c nodes that: G β S planar.
a) Give an example graph G with a maximum of 10 nodes that canβt be made 2planar but 3planar.
Show that your example is correct by selecting a set π β V(G) of Cardinality 3 so that GS
planar.
b) G is a Graph that can be made 5planar. How many pairwise nodedisjoint copies of πΎ5 can G
contain at a maximum. Provide the best boundaries and reasons for your answer.
c) G is a Graph with π β β  blocks, all blocks are able to be made into cplanars. How many pairwise
nodedisjoint copies of πΎ5 can G contain at a maximum? State the best boundaries in dependency
to b and c plus your reasoning behind it.
d) G being a graph and B a block from G, prove π₯
(πΊ) = πππ₯π΅βGπ₯
(π΅)
8) X is a finite set with n:= π. A set πΉ β π(π) is a Clutter, if for all π΄,π΅ β πΉ applies: If π΄ β π΅ then A=B
a) X:={1,2,3,4}. State a Clutter πΉ β π(π) with πΉ = (
4
2
)
b) Clutter πΉ β π(π). Show that πΉ β€ (
π

π
2

)
9) X is a finite set with n:= π. A set πΉ β π(π) is a Clutter.
F is simple, if for all π΄, π΅ β πΉ with π΄ β π΅ applies: π΄ β© π΅ β€ 1 and π΄ β₯ 2.
F is forestlike, if for all subfamilies π β πΉ an π΄ β π and an element π β π΄ exists, that π΅ β π
with π΄ β π΅ applies: if π΄ β© π΅ β 0 then π΄ β© π΅ = {π}.
C β π(π) is a set that is a subset of X. A real 2colouring of C is a transformation f:X>{red,blue},
so that π΄ β πΆ applies π΄ β© π
β1
({πππ}) β 0 and π΄ β© π
β1
({πππ’π}) β 0.
a) G is a connected graph with a minimum of 2 nodes. We define the following set:
π΅(πΊ) β {π(π΅)π΅ β πΊ and π΅ is a block from πΊ} β π(π(πΊ))
Prove that B(G) is a simple and forestlike Clutter.
b) Show that there is a real 2colouring for every simple and forestlike Clutter πΉ β π(π).