Paperlane

no. 7 · Tuesday 3 November 2026

Contractable 2-connected subgraphs in minimally 3-connected graphs

Rongchuan Tao

math.CO · 11 pp

Abstract

We study the 2-connected subgraphs of minimally 3-connected graphs whose contraction preserves 3-connectedness. We show that every minimally 3-connected graph that is not a wheel or a complete bipartite graph $K_{3,n}$ contains a contractable 2-connected induced subgraph that is a cycle, a fan, a $K_{2,n}$ or a $K_{3,n}$. In addition, these subgraphs satisfy certain degree restrictions. We show that none of these four families can be discarded since for each one of the four families, there exists a minimally 3-connected graph containing a contractable induced 2-connected subgraph in that family and none in the other three families. Reversing the contraction process gives a new construction for 3-connected graphs using edge addition, expansions into prescribed 2-connected subgraphs and $Y$-sum.

comments
11 pages, 5 figures, submitted to Journal of Graph Theory
fields
Combinatorics
pdf ↗ page arXiv:2611.01588 ↗