DisMat UE 01

ex1-0.pdf
Diskrete_Mathematik_Lösung_UE_01-0.pdf

Exercise 1.1

A graph is called self-complementary if it is isomorphic to its own complement.

1. Show that when G is self-complementary on n vertices,
   we have $n\equiv 0$ or $n\equiv 1mod4$. (3 Punkte)

$$E(G)=E(\overline{G})$$

Die Menge aller Kanten ist:

$$\frac{n(n-1)}{2}=|E(G)|$$

Damit $|E(G)|$ gerade ist muss $n$ oder $n-1$ durch 4 teilbar sein,
da nicht beide gerade sein können.

2. Find all self-complementary graphs with at most 4 vertices. (3 Punkte)

all Graphs with no edges:

1. $V=\varnothing ,E=\varnothing$
2. $V=\{a\},E=\varnothing$
3. $V=\{a,b\},E=\varnothing$
4. $V=\{a,b,c\},E=\varnothing$
5. $V=\{a,b,c,d\},E=\varnothing$
   proof: $\overline{E}=\varnothing =E$

all Graphs that form a Z:

1. $V=\{a,b,c,d\},E=\{(a,b),(b,c),(c,d)\}$
2. $V=\{a,b,c,d\},E=\{(a,b),(a,d),(c,d)\}$
3. $V=\{a,b,c,d\},E=\{(a,c),(a,d),(b,d)\}$
4. $V=\{a,b,c,d\},E=\{(a,c),(b,c),(b,d)\}$
   proof:
   the compliment also forms a rotated Z:

DisMat UE 01 1.excalidraw

1.2

Angenommen die Bücher werden möglichst gleichmäßig gewählt.
Wenn jedes der 23 title 3 mal gewählt werden würde dann wären das nur
$3\ast 23=69$ Wahlen.
Da $7\ast 10=70$ Bücher gewählt werden muss ein Buch 4x gewählt werden.

1.3

Each year is chosen at least $\lceil (4100\cdot 7)/2025\rceil =15$ times.
We round up because each year is chosen the same number.
$15/7>2$ so there must be a day with 3 people.