A recursive characterization of the 4-connected graphs (Q2277470): Difference between revisions

A graph is said to be contraction critical if the contraction of any edge decreases its connectivity. It being known that, for \(n=2\) and 3, the only contraction critical graph of connectivity n is \(K_{n+1}\), the author characterizes the 4-connected contraction critical graphs as the 4-valent graphs every edge of which lines on a 3-circuit. These graphs are presented in an earlier paper by the author [J. Graph Theory 6, 343- 344 (1982; Zbl 0499.05041)] and a still earlier paper of \textit{M. Fontet} [C. R. Acad. Sci. Paris, Sér. A 287, 289-290 (1978; Zbl 0386.05039)].