Unavoidable parallel minors of 4‐connected graphs

A parallel minor is obtained from a graph by any sequence of edge contractions and parallel edge deletions. We prove that, for any positive integer k , every internally 4‐connected graph of sufficiently high order contains a parallel minor isomorphic to a variation of K 4, k with a complete graph on the vertices of degree k , the k ‐partition triple fan with a complete graph on the vertices of degree k , the k ‐spoke double wheel, the k ‐spoke double wheel with axle, the (2k+1)‐rung Möbius zigzag ladder, the (2 k )‐rung zigzag ladder, or K k . We also find the unavoidable parallel minors of 1‐, 2‐, and 3‐connected graphs. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 313‐326, 2009