A Constructive Characterization of 4-Connected Graphs

Let k be an integer such that k >= 3. Let H-k denote the set of k-connected graphs each G of which has a vertex x such that G - x is a (k - 1)-connected (k - 1)-regular graph. Note that H-3 is the set of wheels. Let G be a k-connected graph where k >= 2 is an integer. An operation on G is defined as follows. (I) Delete a vertex x of degree at least 2(k - 1) from G, (II) Add new two vertices x(1) and x(2), (III) Join x(i) to N-i boolean OR {x(3-i)} for i = 1, 2 where N-G(x) = N-1 boolean OR N-2, vertical bar N-i vertical bar >= k - 1 for i = 1, 2 and N-1 boolean AND N-2 = empty set. We call this operation "proper vertex-splitting". Two edges of a graph are said to be "independent" if they have no common end vertex and a set of edges is said to be "independent" if each two of it are independent. Let G be a 2k-connected graph where k is a positive integer. We define an operation on G as follows. (I) Choose independent k edges of G, (II) Subdivide each of the chosen k edges by one vertex, (III) Identify the new k vertices arising from the subdivisions. We call this operation "edge-binding". Tutte gave a constructive characterization of 3-connected graphs. Theorem (Tutte's wheel theorem, 1961) Every 3-connected graph can be obtained from a graph in H-3 by repeated applications of edge addings and proper vertex-splittings. In this paper we prove the following 4-connected analogue of Tutte's Wheel Theorem. Theorem Every 4-connected graph can be obtained from a graph in H-4 by repeated applications of edge addings, proper vertex-splittings and edge-bindings.