  Motivated by the theorem of Gy\H ori and Lov\'asz, we consider the following
problem. For a connected graph $G$ on $n$ vertices and $m$ edges determine the
number $P(G,k)$ of unordered solutions of positive integers $\sum_{i=1}^k m_i =
m$ such that every $m_i$ is realized by a connected subgraph $H_i$ of $G$ with
$m_i$ edges such that $\cup_{i=1}^kE(H_i)=E(G)$. We also consider the
vertex-partition analogue.
  We prove various lower bounds on $P(G,k)$ as a function of the number $n$ of
vertices in $G$, as a function of the average degree $d$ of $G$, and also as
the size $\mathrm{CMC}_r(G)$ of $r$-partite connected maximum cuts of $G$.
Those three lower bounds are tight up to a multiplicative constant.
  We also prove that the number $\pi(G,k)$ of unordered $k$-tuples with
$\sum_{i=1}^kn_i=n$, that are realizable by vertex partitions into $k$
connected parts of respective sizes $n_1,n_2,\dots,n_k$, is $\Omega(d^{k-1})$.
