Vertex suppression in 3‐connected graphs

Abstract To suppress a vertex $v$ in a finite graph G means to delete it and add an edge from a to b if a , b are distinct nonadjacent vertices which formed the neighborhood of $v$ . Let $G--x$ be the graph obtained from $G-x$ by suppressing vertices of degree at most 2 as long as it is possible; this is proven to be well defined. Our main result states that every 3‐connected graph G has a vertex x such that $G -- x$ is 3‐connected unless G is isomorphic to $K_{3,3}$ , $K_2 \times K_3$ , or to a wheel $K_{1}*C_{\ell}$ for some $\ell \geq 3$ . This leads to a generator theorem for 3‐connected graphs in terms of series parallel extensions. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 41–54, 2008