Edge-cuts leaving components of order at least three (Q1849951)

A graph \(G\) is said to be \(\lambda_p\)-edge connected if there is a set of edges whose removal breaks the graph into connected components each of cardinality at least \(p\). The minimum cardinality of such a cut, if it exists, is the order-\(p\) edge connectivity of \(G\). Under the name of extraconnectivity, this notion was studied in a series of papers [see \textit{J. Fàbrega} and \textit{M. A. Fiol}, Discrete Math. 155, 49-57 (1996; Zbl 0857.05064) and the references therein]. In the present paper the authors prove that a graph \(G\) of order \(n\geq 6\) is \(\lambda_3\)-edge connected unless it consists of a vertex incident with a number of triangles and/or paths of length at most three, with one additional single exception when \(n=6\). Then they show that \(\lambda_3 (G)\) is at most the minimum number of edges emanating from a set of three vertices which induce a connected graph. It is pointed out that a similar statement is no longer true for \(p\geq 4\).