✦ LIBER ✦

Almost All 3-Connected Graphs Contain a Contractible Set of k Vertices

✍ Scribed by Matthias Kriesell

Publisher: Elsevier Science
Year: 2001
Tongue: English
Weight: 223 KB
Volume: 83
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.2001.2060

No coin nor oath required. For personal study only.

✦ Synopsis

McCuaig and Ota conjectured that every sufficiently large 3-connected graph G contains a connected subgraph H on k vertices such that G&V(H) is 2-connected. We prove the weaker statement that every sufficiently large 3-connected graph G contains a not necessarily connected subgraph H on k vertices such that G&V(H) is 2-connected.