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 ∪ { x 3 - i } for i = 1 , 2 where N G (x) = N 1 ∪ N 2 , | N i | ≥ k - 1 for i = 1 , 2 and N 1 ∩ N 2 = ∅. 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. [ABSTRACT FROM AUTHOR]