RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. POMI, 2022 Volume 518, Pages 5–93 (Mi znsl7292)

This article is cited in 1 paper

Every $3$-connected graph on at least $13$ vertices has a contractible set on $5$ vertices

N. Yu. Vlasova

St. Petersburg Department of Steklov Mathematical Institute of Russian Academy of Sciences

Abstract: A subset $H$ of the set of vertices of a $3$-connected finite graph $G$ is called contractible if $G(H)$ is connected and $G - H$ is $2$-connected. We prove that every $3$-connected graph on at least $13$ vertices has a contractible set on $5$ vertices. And there is a $3$-connected graph on $12$ vertices that does not contain a contractible set on $5$ vertices.

Key words and phrases: connectivity, $3$-connected graph, contractible subgraph.

UDC: 519.173.1

Received: 26.09.2022



© Steklov Math. Inst. of RAS, 2025