The Setting
Take a graph on a finite vertex set and pairwise disjoint sets of its vertices, , each large compared with the degrees of its vertices and with the number of neighbours any vertex has in it. Pair up the vertices inside each and identify each pair to a single vertex. An edge inside a pair becomes a loop, and two edges whose ends land on the same two vertices become parallel. The question is how few edges of must be set aside, for a good choice of the pairings, for the rest to fold onto a simple graph. This is Lemma 6.1 of the preprint, the pair folding lemma.
Pairings and the Fold Map
A pairing of a finite set is a fixed-point-free involution of , a map with and for every .✦ The pairs of are the classes of the equivalence relation on given by (1)✦ The quotient of by is the set of pairs of ✦, and the projection sends each to its pair ✦.
For a finite set of vertices, the padded set is itself when is even and with one new element added when is odd. A pairing of pairs up the vertices of and leaves of them unpaired, the vertex when is odd✦.
The outside set of pairwise disjoint vertex sets of is the set of vertices of lying in none of them.✦ For with a pairing of , the folded vertex set of is (2)✦ and the fold map is given by (3)✦
The Claim
Theorem 1. Let be a graph on a finite vertex set , let be pairwise disjoint subsets of , , with , and let be a real number. Suppose that for every , that every vertex of has degree , and that every vertex of has at most neighbours in each , . Then there are pairings of the padded sets , a set of retained edges and a graph on the folded vertex set of (2) such that, with the fold map (3), (4)✦ and every edge of is for exactly one edge of .
In the paper, the result reads: if is a finite simple graph, are pairwise disjoint subsets of , , , for every in and for every and , then there are pairings within the , each leaving exactly vertices unpaired, and a set with such that identifying each pair in gives a simple graph in which every edge has exactly one retained original edge as representative and , and this holds also when the family is empty. The paper’s is , and its pairings within the are the pairings of the padded sets .
What Is Checked
The claim (4) is stated over a graph on a finite vertex set with pairwise disjoint vertex sets , the numbers of neighbours in them, the pairings of the padded sets with their quotients by the pair relation (1), the outside set , the folded vertex set and the fold map . The library also proves that, for pairwise disjoint , the map from the disjoint union of to that sends each element to itself is a bijection.✦