Removable edges in a 5-connected graph and a construction method of 5-connected graphs

An edge e of a k-connected graph G   is said to be a removable edge if G⊖eG⊖e is still k-connected. A k-connected graph G   is said to be a quasi (k+1)(k+1)-connected if G has no nontrivial k-separator. The existence of removable edges of 3-connected and 4-connected graphs and some properties of quasi k  -connected graphs have been investigated [D.A. Holton, B. Jackson, A. Saito, N.C. Wormale, Removable edges in 3-connected graphs, J. Graph Theory 14(4) (1990) 465–473; H. Jiang, J. Su, Minimum degree of minimally quasi (k+1)(k+1)-connected graphs, J. Math. Study 35 (2002) 187–193; T. Politof, A. Satyanarayana, Minors of quasi 4-connected graphs, Discrete Math. 126 (1994) 245–256; T. Politof, A. Satyanarayana, The structure of quasi 4-connected graphs, Discrete Math. 161 (1996) 217–228; J. Su, The number of removable edges in 3-connected graphs, J. Combin. Theory Ser. B 75(1) (1999) 74–87; J. Yin, Removable edges and constructions of 4-connected graphs, J. Systems Sci. Math. Sci. 19(4) (1999) 434–438]. In this paper, we first investigate the relation between quasi connectivity and removable edges. Based on the relation, the existence of removable edges in k  -connected graphs (k⩾5k⩾5) is investigated. It is proved that a 5-connected graph has no removable edge if and only if it is isomorphic to K6K6. For a k-connected graph G such that end vertices of any edge of G   have at most k-3k-3 common adjacent vertices, it is also proved that G   has a removable edge. Consequently, a recursive construction method of 5-connected graphs is established, that is, any 5-connected graph can be obtained from K6K6 by a number of θ+θ+-operations. We conjecture that, if k is even, a k-connected graph G   without removable edge is isomorphic to either Kk+1Kk+1 or the graph Hk/2+1Hk/2+1 obtained from Kk+2Kk+2 by removing k/2+1k/2+1 disjoint edges, and, if k is odd, G   is isomorphic to Kk+1Kk+1.