Removable edges in a kk-connected graph and a construction method for kk-connected graphs

An edge ee of a kk-connected graph GG is said to be a removable edge   if G⊖eG⊖e is still kk-connected, where G⊖eG⊖e denotes the graph obtained from GG by deleting ee to get G−eG−e and, for any end vertex of ee with degree k−1k−1 in G−eG−e, say xx, deleting xx and then adding edges between any pair of non-adjacent vertices in NG−e(x)NG−e(x). Xu and Guo [Liqiong Xu, Xiaofeng Guo, Removable edges in a 5-connected graph and a construction method of 5-connected graphs, Discrete Math. 308 (2008) 1726–1731] proved that a 5-connected graph GG has no removable edge if and only if G≅K6G≅K6, using this result, they gave a construction method for 5-connected graphs. A kk-connected graph GG is said to be a quasi (k+1)(k+1)-connected if GG has no nontrivial kk-vertex cut. Jiang and Su [Hongxing Jiang, Jianji Su, Minimum degree of minimally quasi (k+1)(k+1)-connected graphs, J. Math. Study 35 (2002) 187–193] conjectured that for k≥4k≥4 the minimum degree of a minimally quasi kk-connected graph is equal to k−1k−1. In the present paper, we prove this conjecture and prove for k≥3k≥3 that a kk-connected graph GG has no removable edge if and only if GG is isomorphic to either Kk+1Kk+1 or (when kk is even) the graph obtained from Kk+2Kk+2 by removing a 1-factor. Based on this result, a construction method for kk-connected graphs is given.