Key points are not available for this paper at this time.
Abstract Motivated by the theorem of Győri and Lovász, we consider the following problem. For a connected graph on vertices and edges determine the number of unordered solutions of positive integers such that every is realized by a connected subgraph of with edges. We also consider the vertex‐partition analogue. We prove various lower bounds on as a function of the number of vertices in , as a function of the average degree of , and also as the size of ‐partite connected maximum cuts of . Those three lower bounds are tight up to a multiplicative constant. We also prove that the number of unordered ‐tuples with , that are realizable by vertex partitions into connected parts, is at least .
Caro et al. (Sun,) studied this question.