Satz von Wagner und Fáry

Der Satz v​on Wagner u​nd Fáry, manchmal a​uch als Satz v​on Wagner o​der Satz v​on Fáry bezeichnet, i​st ein Lehrsatz a​us dem mathematischen Teilgebiet d​er Topologischen Graphentheorie, welcher zuerst i​m Jahre 1936 v​on dem Mathematiker Klaus Wagner gefunden u​nd dann i​m Jahre 1948 v​on dem Mathematiker István Fáry erneut gefunden wurde. Der Satz behandelt e​ine wichtige Eigenschaft plättbarer Graphen, d​ie nicht zuletzt i​m Zusammenhang m​it dem Vierfarbensatz u​nd verwandten mathematischen Lehrsätzen v​on Bedeutung ist.

Formulierung des Satzes

Nach einem geeigneten Homöomorphismus sind auch B und D durch eine Strecke verbunden.

Erste Version

Die e​rste Version d​es Satzes lautet w​ie folgt:[1]

Ist ein endlicher schlichter Graph ${\displaystyle G=(V,E)}$ plättbar, so existiert sogar ein isomorpher ebener Graph ${\displaystyle G'=(V',E')}$ dergestalt, dass die zu den Kanten ${\displaystyle e'\in E'}$ gehörigen Jordankurven sämtlich abgeschlossene Strecken sind, die einander nie in einem inneren Punkt kreuzen, also paarweise stets höchstens einen der Knoten ${\displaystyle v'\in V'}$ gemeinsam haben.

Zweite Version

Ein ebener Graphen ${\displaystyle G'=(V',E')}$ der in der ersten Version genannten Art wird auch als Streckengraph oder als geradlinige Darstellung (des Graphen ${\displaystyle G}$) bezeichnet. Unter Verwendung dieser Begriffe lässt sich der Satz auch folgendermaßen formulieren:[2][3]

Jeder ebene Graph kann durch einen Homöomorphismus der euklidischen Ebene auf sich in einen Streckengraphen überführt werden.

Anmerkungen

• Die Bedeutung des Satzes von Wagner und Fáry (in der zweiten Version) für den Vierfarbensatz geht aus einer Anmerkung hervor, die der Mathematiker Rudolf Fritsch in seiner Monographie Der Vierfarbensatz dazu macht. Fritsch schreibt, dass der Satz die endgültige Befreiung aus dem Gruselkabinett beliebiger Jordankurven bringt und den Vierfarbensatz aus den Klauen der allgemeinen Topologie löst.[4]
• Die Vermutung, dass die Aussage des Satzes von Wagner und Fáry gelte, wurde István Fáry zufolge schon früher von dem ungarischen Mathematiker Tibor Szele geäußert.[4]

Siehe auch

• Äquivalenzsatz von Wagner
• Satz von Wagner

Literatur

• István Fáry: On straight line representation of planar graphs. In: Acta Univ. Szeged. Sect. Sci. Math. Band 11, 1948, S. 229–233 (MR0026311).
• Rudolf Fritsch: Der Vierfarbensatz. Geschichte, topologische Grundlagen und Beweisidee. Unter Mitarbeit von Gerda Fritsch. BI Wissenschaftsverlag, Mannheim / Leipzig / Wien / Zürich 1994, ISBN 3-411-15141-2 (MR1270673).
• Rudolf Halin: Graphentheorie II (= Erträge der Forschung. Band 161). Wissenschaftliche Buchgesellschaft, Darmstadt 1981, ISBN 3-534-08269-9 (MR0668698).
• Nora Hartsfield, Gerhard Ringel: Pearls in Graph Theory. A Comprehensive Introduction. Academic Press, Boston (u. a.) 1990, ISBN 0-12-328552-6 (MR1069559).
• Jonathan L. Gross, Thomas W. Tucker: Topological Graph Theory (= Wiley-Interscience Series in Discrete Mathematics and Optimization). John Wiley & Sons, New York 1987, ISBN 0-471-04926-3 (MR0898434).
• Klaus Wagner: Bemerkungen zum Vierfarbenproblem. In: Jahresbericht der Deutschen Mathematiker-Vereinigung. Band 46, 1936, S. 26–32.
• Klaus Wagner: Graphentheorie (= BI-Hochschultaschenbücher. 248/248a). Bibliographisches Institut, Mannheim (u. a.) 1970, ISBN 3-411-00248-4 (MR0282850).

Einzelnachweise und Anmerkungen

1. Nora Hartsfield, Gerhard Ringel: Pearls in Graph Theory. 1990, S. 166–167
2. Rudolf Fritsch: Der Vierfarbensatz. 1994, S. 106 ff., 113–115
3. Rudolf Halin: Graphentheorie II. 1981, S. 9 ff., 14–15
4. Fritsch, op. cit., S. 107