The Setting
Let the edges of a graph be split among edge-disjoint graphs , the edges of lying inside a vertex set . When every is small, there may be many such graphs. The question is how few graphs, each with its edges inside a set of at most vertices, for a positive real number , the edges of can be split among instead, if the sizes of these sets are to add up to no more than . The library answers it when every has at most vertices.
Pieces and Batches
A piece on the vertex set of is a graph together with a set of vertices that contains both ends of every edge of ; may hold vertices that meet no edge of . The order of the piece is .
Let be a set of vertices of , and let and be real numbers. A batch family for , , and is a finite family of pieces , , the batches, in which the are subgraphs of whose edge sets are pairwise disjoint with union , the sets lie in and cover it, and (1)✦
The Claim
Theorem 1. Let be a graph, a set of its vertices and a positive real number. Let , , be a finite family of pieces such that the edge sets of the are pairwise disjoint with union , the sets lie in and cover it, and every piece has order at most . Then (2)✦
What Is Checked
The claim (2) is stated over a graph , a vertex set , a positive real number , a finite family of pieces whose graphs split the edges of edge-disjointly and whose sets lie in , cover it and have at most elements each, and the batch families of (1).