We show that the only graphs with certain connectivity and planarity properties are the Petersen graph and some other more trivial graphs. Then this is used to show that every graph with no minor in the Petersen family (the seven graphs that can be obtained from the Petersen graph by Y - Δ and Δ - Y exchanges) is either decomposable in some sense, or it is a 1-vertex extension of a planar graph, or it has high connectivity in a sense we can use, or it can be converted to one of these by Y - Δ and Δ - Y exchanges. This is a lemma for use in a subsequent paper, where we show that a graph has a “linkless” embedding in 3-space if and only if it has no minor in the Petersen family.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics