Übungen

Übung 1

Sei n ≥ 1. Geben Sie eine planare Darstellung des vollständig bipartiten Graphen K_2, n an, die nur gerade Kanten verwendet.

Übung 2

Sei G = (E, K) ein planar dargestellter Graph mit den Flächen f₁, …, f_m. Für jede Fläche f_i sei g(f_i) die Anzahl der Kanten von G, die die Fläche f_i begrenzen. Weiter sei k_b die Anzahl der Brücken von G. Zeigen Sie:

∑_{1 ≤ i ≤ m} g(f_i) = 2|K| − k_b.

Übung 3

Zeigen Sie (durch anschauliche geometrische Argumentation):

(a)	Jede planare Darstellung des K₄ hat die Form eines Dreiecks mit einer Ecke innerhalb des Dreiecks.

(b)	Zeigen Sie mit Hilfe von (a), dass der Graph K₅ nicht planar ist.

(c)	Zeigen Sie in ähnlicher Weise, dass der Graph K_3, 3 nicht planar ist.

Übung 4

(a)	Beweisen Sie die Eulersche Polyederformel für zusammenhängende Graphen durch Induktion über die Anzahl der Flächen.

(b)	Beweisen Sie die allgemeine Eulersche Polyederformel mit Hilfe der Aussage (a) durch Induktion über die Anzahl der Zusammenhangskomponenten.

Übung 5

Zeigen Sie:

(a)	Es gibt einen planaren Graphen der Ordnung 12, der die konstante Gradfolge 5, …, 5 besitzt.

(b)	Es gibt keinen planaren Graphen der Ordnung n < 12, der die konstante Gradfolge 5, …, 5 besitzt.

Übung 6

Wo scheitert der Beweis, wenn wir versuchen, das Argument des Fünffarbensatzes zu verwenden, um den Vierfarbensatz zu zeigen?

Übung 7

Nach dem Vierfarbensatz ist jeder planare Graph 4-färbbar. Gilt auch die Umkehrung, d. h. ist jeder 4-färbbare Graph planar?

Übung 8

Sei G = (E, K) ein planar dargestellter Graph. Wir ordnen der Darstellung den dualen Graphen G* = (E*, K*), einen Graphen mit möglichen Mehrfachkanten und Schlingen, zu, indem wir Flächen als Ecken und Kanten als Kanten zwischen angrenzenden Flächen auffassen. Genauer gilt:

(i)	E* ist die Menge der Flächen der Darstellung von G.

(ii)	Jede Kante ab von K entspricht genau einer Kante F₁ F₂ von G* und umgekehrt, wobei F₁ und F₂ die Flächen links und rechts der Kante ab sind.

Es gilt also |K| = |K*|. Die Brücken von G entsprechen genau den Schlingen von G*.

(a)	Geben Sie instruktive Beispiele für duale Graphen.

(b)	Welche Struktureigenschaften von G führen zu Mehrfachkanten?

(c)	Welche allgemeinen Eigenschaften können Sie für duale Graphen feststellen?

(d)	Bestimmen Sie die dualen Graphen der Graphen der Platonischen Körper.

(e)	Zeigen Sie, dass es einen zusammenhängenden planaren Graphen G und zwei Darstellungen von G gibt, deren duale Graphen nicht isomorph zueinander sind.