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

Zap. Nauchn. Sem. POMI, 2018 Volume 475, Pages 22–40 (Mi znsl6684)

This article is cited in 1 paper

On contractible 5-vertex subgraphs of a 3-connected graph

N. Yu. Vlasova

St. Petersburg State University, Mathematics and Mechanics Faculty, St. Petersburg, Russia

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 $11$ vertices with minimal degree at least $4$ has a contractible set on $5$ vertices.

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

UDC: 519.173.1

Received: 12.11.2018



© Steklov Math. Inst. of RAS, 2025