2011/01/24 by Vadim E. Levit, Levit, Vadim E., Eugen Mândrescu +2
Computer Science · Mathematics · #05C69 #05C70 (Primary) 05A20(Secondary) #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.2 #Limits and Structures in Graph Theory #acm:05C69 #acm:05C70 #cs.DM #math.CO #msc:05C69 #msc:05C70
paper · pdf · doi:10.48550/arxiv.1101.4564
7 pages, 3 figures
openalex publication_date 2011/01/24 · arxiv created 2011/08/25 · arxiv updated 2011/08/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A set S is independent if no two vertices from S are adjacent. In this paper we prove that if F is a collection of maximum independent sets of a graph, then there is a matching from S-intersection of all members of F into union of all members of F-S, for every independent set S. Based on this finding we give alternative proofs for a number of well-known lemmata, as the "Maximum Stable Set Lemma" due to Claude Berge and the "Clique Collection Lemma" due to András Hajnal.