Cycles are the only connectivity double-critical graphs

Abstract

For a graph G, its connectivity and edge-connectivity are denoted by K(G) and K'(G), respectively. In this note, we show that for a graph G of order n, K'(G — e\ — ei) = n'{G) — 2 (or K(G - ei - ez) = K(G) - 2) for any pair of edges ei, e₂ € E(G) if and only if G = C_N © 2020 Utilitas Mathematica Publishing Inc.. All rights reserved.