Planar graphs with no 6-wheel minor (Q687108): Difference between revisions

By Tutte's wheels theorem [Nederl. Akad. Wet., Proc. Ser. A 64, 441-455 (1961; Zbl 0101.409)], every simple 3-connected graph can be built from some wheel graph by adding edges and splitting vertices. Moreover, \textit{B. Oporowski}, \textit{J. Oxley} and \textit{R. Thomas} [J. Comb. Theory, Ser. B 57, 239-257 (1993; Zbl 0728.05041)] showed that, for all \(n\geq 3\), there are only finitely many simple 3-connected planar graphs having no minor isomorphic to the \(n\)-spoked wheel \(W_ n\). However, the last paper made no attempt to give a practical bound on the size of a largest simple 3-connected planar graph with no \(W_ n\)-minor. In the present paper, the author lists thirty-eight graphs, each with sixteen or seventeen edges, and shows that every simple 3-connected planar graph with no \(W_ 6\)-minor is a minor of one of these thirty-eight graphs. As a consequence of this, he shows that, for all \(m\geq 3\), an \(m\)-vertex simple planar graph with no \(W_ 6\)-minor has at most \(\lceil (14m-27)/5 \rceil\) edges with this bound being attained for all \(m\).