  A simple graph $G=(V,E)$ on $n$ vertices is said to be recursively
partitionable (RP) if $G \simeq K_1$, or if $G$ is connected and satisfies the
following recursive property: for every integer partition $a_1, a_2, \dots,
a_k$ of $n$, there is a partition $\{A_1, A_2, \dots, A_k\}$ of $V$ such that
each $|A_i|=a_i$, and each induced subgraph $G[A_i]$ is RP ($1\leq i \leq k$).
We show that if $S$ is a vertex cut of an RP graph $G$ with $|S|\geq 2$, then
$G-S$ has at most $3|S|-1$ components. Moreover, this bound is sharp for
$|S|=3$. We present two methods for constructing new RP graphs from old. We use
these methods to show that for all positive integers $s$, there exist
infinitely many RP graphs with an $s$-vertex cut whose removal leaves $2s+1$
components. Additionally, we prove a simple necessary condition for a graph to
have an RP spanning tree, and we characterise a class of minimal 2-connected RP
graphs.

Combinatorics