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)

Definition complementary#

Given: $G=\{V,E\}$
$\overline{G}:=\{V,\overline{E}\}$
$\overline{E}:=\{(v,w)|(v,w)\notin E\}$

Proof $n\equiv 0$

$\varnothing =E_{n\equiv 0}\subseteq \left(\begin{array}{c}\varnothing \\ 2\end{array}\right)$

Proof $n\equiv 1mod4$

$1mod4=1$ ???

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