Back to Search
Start Over
A THEOREM ABOUT A CONTRACTIBLE AND LIGHT EDGE.
- Source :
-
SIAM Journal on Discrete Mathematics . 2006, Vol. 20 Issue 1, p55-61. 7p. 3 Diagrams. - Publication Year :
- 2006
-
Abstract
- In 1955 Kotzig [A. Kotzig, Math. Slovaca, 5 (1955), pp. 111-113] proved that every planar 3-connected graph contains an edge such that the sum of degrees of its end-vertices is at most 13. Moreover, if the graph does not contain 3-vertices, then this sum is at most 11. Such an edge is called light. The well-known result of Steinitz [E. Steinitz, Enzykl. Math. Wiss., 3 (1922), pp. 1-139] that the 3-connected planar graphs are precisely the skeletons of 3-polytopes gives an additional trump to Kotzig's theorem. On the other hand, in 1961, Tutte [W. T. Tutte, Indag. Math., 23 (1961), pp. 441-455] proved that every 3-connected graph, distinct from K4, contains a contractible edge. In this paper, we strengthen Kotzig's theorem by showing that every 3-connected planar graph distinct from K4 contains an edge that is both light and contractible. A consequence is that every 3-polytope can be constructed from tetrahedron by a sequence of splittings of vertices of degree at most 11. [ABSTRACT FROM AUTHOR]
- Subjects :
- *POLYTOPES
*GRAPHIC methods
*CONVEX polytopes
*MATHEMATICS
*POLYNOMIALS
Subjects
Details
- Language :
- English
- ISSN :
- 08954801
- Volume :
- 20
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 25290882
- Full Text :
- https://doi.org/10.1137/05062189X