Aufgabe: 

Es sei $E$ eine Menge von 200 olympischen Athleten und $K=\{\{a,b\} | a,b \in E, a≠b, a,b \enspace haben \enspace dieselbe \enspace Anzahl \enspace an \enspace Medaillen\}$.

Angenommen, es werden 200 Medaillen an die Athleten aus $E$ verliehen. Es sei $G=\{E,K\}$ der Graph mit Eckenmenge $E$ und Kantenmenge $K$. 
 
(a) Ist $G$ planar?
(b) Ist $G$ eulersch, falls $G$ zusammenhängend ist?

Lösung: 

Fall 1: 
Falls diese 200 Medaillen gleich auf alle Athleten verteilt wird, ist $G$ der vollständige Graph $K_{200}$ und nicht planar. Es gilt ja, dass wenn $G$ planar ist $k≤3e-6$, wobei $k$ die Kantenanzahl und $e$ die Eckenanzahl ist. Das heißt, ich kann die Umkehrung dieser Implikation nutzen: Gilt nicht $k≤3e-6$, so ist $G$ nicht planar. 


$\Rightarrow$ ${200 \choose 2} ≤3*200-6$ gilt offensichtlich nicht und deshalb ist $G$ nicht planar. 

Eulersch ist er auch nicht, da alle Ecken Grad $199$ haben, was nicht gerade ist. 


Was mache ich aber in Fall 2: Die 200 Medaillen werden nicht gleich auf die Athleten verteilt?

EDIT vom 29.07.2022 um 20:10:

Würde mich echt freuen, falls jemand rüberschauen kann :)