Theorem by Wagner and Fáry

The Wagner and Fáry Theorem , sometimes also referred to as Wagner's Theorem or Fáry's Theorem , is a doctrine from the mathematical branch of topological graph theory , which was first found in 1936 by the mathematician Klaus Wagner and then in 1948 by the mathematician István Fáry was found again. The theorem deals with an important property of flattenable graphs , which is important not least in connection with the four-color theorem and related mathematical theorems.

Formulation of the sentence

According to a suitable homeomorphism, B and D are also connected by a segment.

First version

The first version of the sentence is as follows:

If a finite, simple graph can be flattened, there is even an isomorphic planar graph in such a way that the Jordan curves belonging to the edges are all closed segments that never cross each other at an inner point , i.e. in pairs they always have at most one of the nodes in common . ${\displaystyle G=(V,E)}$ ${\displaystyle G'=(V',E')}$ ${\displaystyle e'\in E'}$ ${\displaystyle v'\in V'}$

Second version

A planar graphs of the type mentioned in the first version is also called a route graph or as a linear representation (the graph designated). Using these terms, the sentence can also be formulated as follows: ${\displaystyle G'=(V',E')}$ ${\displaystyle G}$

Every plane graph can be converted into a segment graph by a homeomorphism of the Euclidean plane .

Remarks

• The meaning of Wagner and Fáry's theorem (in the second version) for the four-color theorem emerges from a comment made by mathematician Rudolf Fritsch in his monograph The four-color theorem . Fritsch writes that the sentence brings the final liberation from the horror cabinet of arbitrary Jordan curves and releases the four-color sentence from the clutches of general topology .
• According to István Fáry, the presumption that the statement of Wagner and Fáry's theorem is valid was expressed earlier by the Hungarian mathematician Tibor Szele .

See also

• Wagner equivalence theorem
• Wagner theorem

literature

• István Fáry: On straight line representation of planar graphs . In: Acta Univ. Szeged. Sect. Sci. Math. Band 11 , 1948, pp. 229-233 ( MR0026311 ).
• Rudolf Fritsch : The four-color set. History, topological foundations and idea of ​​proof . With the collaboration of Gerda Fritsch. BI Wissenschaftsverlag, Mannheim / Leipzig / Vienna / Zurich 1994, ISBN 3-411-15141-2 ( MR1270673 ).
• Rudolf Halin : Graph Theory II (=  yields of research . Volume 161 ). Scientific Book Society, Darmstadt 1981, ISBN 3-534-08269-9 ( MR0668698 ).
• Nora Hartsfield, Gerhard Ringel : Pearls in Graph Theory . A Comprehensive Introduction. Academic Press, Boston (et al.) 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: Comments on the four-color problem . In: Annual report of the German Mathematicians Association . tape 46 , 1936, pp. 26-32 .
• Klaus Wagner: Theory of graphs (=  BI university pocket books. 248 / 248a). Bibliographisches Institut, Mannheim ( inter alia ) 1970, ISBN 3-411-00248-4 ( MR0282850 ).

References and comments

1. ^ Nora Hartsfield, Gerhard Ringel: Pearls in Graph Theory. 1990, pp. 166-167
2. ↑ Rudolf Fritsch: The four-color set. 1994, pp. 106 ff., 113-115
3. ↑ Rudolf Halin: Graphentheorie II. 1981, p. 9 ff., 14-15
4. ↑ ^{a b} Fritsch, op.cit., P. 107