Counting connected partitions of graphs

Motivated by the theorem of Gy & odblac;ri and Lov & aacute;sz, we consider the following problem. For a connected graph G $G$ on n $n$ vertices and m $m$ edges determine the number P(G,k) $P(G,k)$ of unordered solutions of positive integers & sum;i=1kmi=m ${\sum }_{i=1}<^>{k}{m}_{i}=m$ such that every mi ${m}_{i}$ is realized by a connected subgraph Hi ${H}_{i}$ of G $G$ with mi ${m}_{i}$ edges. We also consider the vertex-partition analogue. We prove various lower bounds on P(G,k) $P(G,k)$ as a function of the number n $n$ of vertices in G $G$, as a function of the average degree d $d$ of G $G$, and also as the size CMCr(G) $CM{C}_{r}(G)$ of r $r$-partite connected maximum cuts of G $G$. Those three lower bounds are tight up to a multiplicative constant. We also prove that the number pi(G,k) $\pi (G,k)$ of unordered k $k$-tuples with & sum;i=1kni=n ${\sum }_{i=1}<^>{k}{n}_{i}=n$, that are realizable by vertex partitions into k $k$ connected parts, is at least Omega(dk-1) ${\rm{\Omega }}({d}<^>{k-1})$.