Vollständiger bipartiter Graph/3/Nicht planar/Beispiel

Aus Wikiversity
Zur Navigation springen Zur Suche springen

Der vollständige bipartite Graph ist nicht planar. Er besitzt Knotenpunkte und Kanten. Wenn er planar wäre, so müsste es nach der eulerschen Polyederformel Gebiete geben. Jedes dieser Gebiete wird durch einen Kreis berandet, und diese haben nach Fakt eine gerade Länge. Deshalb liegen an jedes Gebiet zumindest Kanten an. Da jede Kante nur an Gebieten beteiligt ist, braucht man zumindest Kanten, ein Widerspruch.