Aufgabe:
Ein planarer Graph \( G=(V, E) \) mit \( |V|=n \) Knoten heißt Triangulation, wenn jedes seiner Gebiete (einschlieflich des unbeschränkten Gebietes) von genau drei Kanten umschlossen wird (ako dessen Rand ein Kreis der Länge 3 ist. Beweisen Sie die folgenden Aussagen:
a) Ist \( G \) planar und hat genau \( 3 n-6 \) Kanten, so ist \( G \) maximal planar, d.h. \( G \) ist planar und durch das Hinzuftgen einer beliebigen Kante ist \( G \) nicht mehr planar.
b) Ist G maximal planar, so ist \( G \) eine Triangulat ion.
c) Ist \( G \) eine Triangulation, so ist \( G \) planar und hat genau \( 3 n-6 \) Kanten.
