A constructive characterization of 4-connected graphs (Q2157839)

Let \(\mathcal{H}_4\) be the set of \(4\)-connected graphs \(G\) such that \(G\) contains a vertex \(x\) such that \(G-x\) is a \(3\)-regular \(3\)-connected graph. Let \(G\) be a \(4\)-connected graph. We call the following operation ``proper vertex-splitting'': (I) delete a vertex \(x\) of degree at least \(6\) from \(G\), (II) add new two vertices \(x_1\) and \(x_2\), (III) for \(i=1,2\), join \(x_i\) to \(N_i\cup \{x_{3-i}\}\), where \(N_G(x)=N_1\cup N_2\), \(|N_i|\geq 3, N_1\cap N_2=\emptyset\). We also call the following operation ``edge-binding'': (I) choose a pair of independent edges \(e_1\), \(e_2\), (II) subdivide each \(e_i\) by one vertex \(v_i\) for \(i=1,2\), (III) identify \(v_1\) and \(v_2\). In this article, the author proves that every \(4\)-connected graph can be obtained from a graph in \(\mathcal{H}_4\) by repeated applications of edge adding, proper vertex-splittings, and edge-bindings.