2011/01/27 by Matthias Kriesell, Kriesell, Matthias
Computer Science · Mathematics · #05c75 (Primary) 05c83 (Secondary) #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #math.CO #msc:05c75 #msc:05c83 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1101.5278
IMADA-preprint-math, 25 pages
arxiv created 2011/01/27 · openalex publication_date 2011/01/27 · arxiv updated 2011/01/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We first prove that for every vertex x of a 4-connected graph G there exists a subgraph H in G isomorphic to a subdivision of the complete graph K4 on four vertices such that G-V(H) is connected and contains x. This implies an affirmative answer to a question of W. Kuehnel whether every 4-connected graph G contains a subdivision H of K4 as a subgraph such that G-V(H) is connected. The motor for our induction is a result of Fontet and Martinov stating that every 4-connected graph can be reduced to a smaller one by contracting a single edge, unless the graph is the square of a cycle or the line graph of a cubic graph. It turns out that this is the only ingredience of the proof where 4-connectedness is used. We then generalize our result to connected graphs of minimum degree at least 4, by developing the respective motor: A structure theorem for the class of simple connected graphs of minimum degree at least 4.