Connected partitions of bounded degree graphs with parts of bounded sizes

Question

A connected partition of a graph is a partition of its vertex-set such that the induced subgraph on each part is connected.

Question 1: Are there real numbers $c\ge1$ and $r\ge1$ such that for any positive integer $k$, every sufficiently large finite connected graph with maximum degree $\Delta$ has a connected partition where each part has at least $k$ and at most $c k^r$ vertices?

Question 2: What if we replace "graph" with "hypergraph", where every vertex is contained in at most $\Delta$ hyperedges and every hyperedge contains at most $\Delta$ vertices?

---

The answer is yes when the graph $G$ is a tree. To see this, pick a vertex $v$ and treat it as the root of the tree $G$. Set $V_1 = \{v\}$. Add a neighbour of $V_1$ to $V_1$ recursively until $V_1$ has $k$ vertices or there are no more vertices to add.

For each neighbour of $V_1$ obtained above, consider the rooted subtree "below" it. Repeat the above procedure for each such subtree "below" $V_1$. Then repeat the above steps for the subtrees below those subtrees and so on.

Whenever a $V_{i\ne 1}$ has fewer than $k$ vertices, add it to the $V_j$ "above" it. Since $V_j$ has exactly $k$ vertices, it has at most $k\Delta$ neighbours, so in the end, each remaining $V_i$ would have at least $k$ vertices and at most $k + \Delta k^2\le (1+\Delta) k^2$ vertices. Moreover, by construction, the induced subgraph on each remaining $V_i$ is connected.

Therefore, when the graph is a tree, $c=\Delta+1$ and $r=2$ works. Importantly, these numbers are all independent of the number of vertices in the tree.

---

I believe something like this should work for any arbitrary graph (and also for hypergraphs), but I don't know how to prove this. Any help is much appreciated.

---

Update 1: As dbal pointed out in the comment below, given the result for trees, one can simply take a spanning tree of the graph and obtain a partition with the desired properties. So question 1 has a positive answer.

I’m not yet sure how this generalises to question 2. The above proof of trees also works for hypergraphs that are “tree-like” (for some reasonable notion of “tree-like”), but I’m not yet sure how to use this result to answer question 2.

Answer 1

As dbal pointed out in a comment to the question, the answer to question 1 is yes.

However, the answer to question 2 is no. For a simple counterexample, consider the following 3-uniform hypergraph: there are $2n$ vertices labelled by $i$ (modulo $2n$), and there is a hyperedge containing three vertices $2j-1$, $2j$, and $2j+1$ (modulo $2n$), for each $j\in \{1,\ldots,n\}$. Then, in any connected partition, there is always a part with just one vertex because every even vertex appears in exactly one hyperedge.