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 :)