Einfacher planaer Graph mit n > 3 Knoten - Beweis

Question

Aufgabe:

Es sei \( G \) ein einfacher planarer Graph mit \( n>3 \) Knoten. Mit \( d_{\max } \) sei der grobte, in \( G \) auftretende Grad bexeichnet und \( n_{i} \) sei die Anzahl der Knoten in \( G \), die den Grad \( i \) besitzen \( \left(0<i<d_{\text {med }}\right) \).

Dann gilt die folgende Ungleichung:

\( 6 n_{0}+5 n_{1}+4 n_{2}+3 n_{3}+2 n_{4}+n_{5}>n_{7}+2 n_{s}+3 n_{9}+\ldots+\left(d_{m a x}-6\right) n_{A_{\text {raas }}}+12 \)

a) Geben Sie ein Beispiel an, indem mindextens 3 Knoten einen Grad \( >6 \) haben.

b) Zeigen Sie, dass die Ausa ge allgemein fuir planare Graphen gilt.

c) Folgern Sie aus dieser Eigenschaft eine Ausage über die Knoten mit Grad \( <5 \) in planaren Graphen.

Answer 1

Von der Uni Karlsruhe gibt es ein Skript, in dem auf Seite 13 zu deinem Problem die Antwort zu finden ist. https://i11www.iti.uni-karlsruhe.de/_media/information/scripts/scripte/algo-plan.pdf

Lemma 2.4. Sei G ein planarer, einfacher Graph mit \( \mathrm{n} \geq 3 \) Knoten, \( \mathrm{d}_{\max }(\mathrm{G}) \) bezeichne den Maximalgrad in \( \mathrm{G} \) und \( \mathrm{n}_{\mathrm{i}} \) die Anzahl der Knoten in \( \mathrm{G} \) mit Grad \( \mathrm{i}, 0 \leq \mathrm{i} \leq \mathrm{d}_{\max }(\mathrm{G}) \). Dann gilt

$$ \begin{aligned} 6 \cdot n_{0}+5 \cdot n_{1}+4 \cdot n_{2}+3 \cdot n_{3}+2 \cdot n_{4}+n_{5} \geq & n_{7}+2 \cdot n_{8}+3 \cdot n_{9}+\cdots+\left(d_{\max }(G)-6\right) \cdot n_{d_{\max }}+12 \end{aligned} $$

Beweis. Offensichtlich ist \( n=\sum \limits_{i=0}^{d_{\max }(G)} n_{i} \) und \( 2 \cdot m=\sum \limits_{i=0}^{d_{\max }}(G) i \cdot n_{i} \).

Da wegen Folgerung \( 2.3 \) gilt, dass \( 6 \mathrm{n} \geq 2 \mathrm{~m}+12 \) ist, folgt

$$ \text { 6. } \sum \limits_{i=0}^{\mathrm{d}_{\max }(\mathrm{G})} \mathrm{n}_{i} \geq \sum \limits_{i=0}^{\mathrm{d}_{\max }(\mathrm{G})} i \cdot n_{i}+12 . $$

Folgerung 2.5. Jeder planare, einfache Graph enthält einen Knoten \( \mathrm{v} \) mit \( \mathrm{d}(v) \leq 5 \).