This question was motivated by a closely related problem An edge partitioning problem on cubic graphsInput: at most cubic graph ( maximum node degree is 3) $G=(V,E)$, a natural number $k$Question: Is there a partition of $E$ into subgraphs isomorphic to $K_{1,2}$ and $K_{1,1}$  such that the sum of the orders of the corresponding subgraphs is exactly $k$ ?Is this problem polynomial time solvable or is it $NP$-complete?Edit: Changed input graph to at most cubic graphs to avoid triviality.
Another edge partitioning problem on cubic graphs
cc.complexity theory;graph theory;np hardness
Perhaps I don't understand the question, but the way I interpret it, Colin's answer seems correct. It is enough to find the minimum possible k for which such partition exists, say k_0. (This is a partition with maximum number of K_21's.) There is a partition for any k between k_0 and 3n/2, because splitting K_21 into two K_11's increases the sum of cardinalities by 1. The K_21's in your partition induce a matching in the line graph of G, so this k_0 corresponds to the maximum matching in the line graph, and this matching can be found in polynomial time.