Steinitz theorem
The set of Steinitz , English Steinitz's theorem , is a mathematical theorem which both the area of the topological graph theory , as well as that of the geometric graph theory is attributable. The sentence stems from a publication of the mathematician Ernst Steinitz (1871-1928) from 1916 and counts along with the Euler Polyedersatz , the Kuratowski's theorem and the theorem of Wagner to the classical results of graph theory on planar graphs .
Formulation of the sentence
The sentence can be stated as follows:
- A finite, simple graph has a straight line representation as - dimensional polyhedron graph if and only if it is flattenable and at the same time -fold connected .
Meaning of the sentence
Steinitz's theorem is one of the fundamental theorems in the doctrine of the polyhedra and apparently Ernst Steinitz himself assessed it that way. As Branko Grünbaum this in his 1975 feature article Polytopal Graphs points out, called Steinitz his sentence, therefore, even as the fundamental theorem of convex types [of polyhedra] ( English Fundamental Theorem of Convex type [of Polyhedra] ) and presented to as many as three elaborate evidence. These are presented in the classic monograph lectures on the theory of polyhedra by Steinitz and Rademacher . How Green Tree continues to write, this representation does not the modern terms served graph theory - such as the relationship or the planarity - but its own terms, which Steinitz 'argument (from today's perspective) quite cumbersome ( English rather cumbersome ) was.
Related sentence
A related theorem, which concerns the polytopes of all higher dimensions and was found by the mathematician Michel Louis Balinski , is the following:
- If a finite, simple graph has a straight line representation as -dimensional polytopgraph in , then it is necessarily -fold connected.
literature
- ML Balinski: On the graph structure of convex polyhedra in n-space . In: Pacific Journal of Mathematics . tape 11 , 1961, pp. 431-434 ( projecteuclid.org ). MR0126765
- Lowell W. Knieke, Robin J. Wilson (Eds.): Topics in Topological Graph Theory (= Encyclopedia of Mathematics and its Applications . Volume 128 ). Cambridge University Press, Cambridge 2009, ISBN 978-0-521-80230-7 ( MR2581536 ).
- Branko Grünbaum : Polytopal Graphs . In: DR Fulkerson (Hrsg.): Studies in Graph Theory (= Mathematical Association of America [Hrsg.]: Studies in Mathematics . Volume 12 ). Part II. Washington DC 1975, ISBN 0-88385-112-1 , pp. 201-224 ( MR0406868 MR0392630 ).
- Frank Harary : Graph Theory . R. Oldenbourg Verlag, Munich, Vienna 1974, ISBN 3-486-34191-X .
- E. Steinitz, H. Rademacher : Lectures on the theory of the polyhedron . Including the elements of topology (= The Basic Teachings of the Mathematical Sciences in Individual Representations . Volume 41 ). Springer Verlag, Berlin / Heidelberg / New York 1976, ISBN 3-540-06293-9 ( MR0430958 - Reprint 1976).
References and footnotes
- ↑ a b Branko Grünbaum: Polytopal Graphs . In: DR Fulkerson (Ed.): Studies in Graph Theory . Part II. 1975, p. 203
- ^ Lowell W. Knieke, Robin J. Wilson: Topics in Topological Graph Theory , 2009, p. 11
- ^ Frank Harary: Grape theory. 1974, p. 115
- ↑ Grünbaum, op.cit., P. 204
- ↑ ML Balinski: On the graph structure of convex polyhedra in n-space. in: Pacific J. Math. 11, pp. 431-434