2016/05/05 by Alexander Hoyer, Hoyer, Alexander, Robin Thomas +1
Computer Science · Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #Topological and Geometric Data Analysis #math.CO
paper · pdf · doi:10.48550/arxiv.1605.01474
4 pages, 1 figure. Corrected spelling of the first author's name
openalex publication_date 2016/05/05 · arxiv created 2016/06/22 · arxiv updated 2016/06/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Gyori and Lovasz independently proved the following beautiful theorem. Let k≥2 be an integer, let G be a k-connected graph on n vertices, let v1,v2,…,vk be distinct vertices of G and let n1,n2,…,nk be positive integers with n1+n2+⋯+nk=n. Then G has disjoint connected subgraphs G1,G2,…,Gk such that for i=1,2,…,k the graph Gi has ni vertices and vi∈ V(Gi). We give a self-contained exposition of Gyori's proof.