# Partition a graph into connected subgraphs of 3 vertices each

We need to partition a graph into subgraphs of 3 vertices each, such that every subgraph has at least 2 edges.

The problem is similar to the partition into triangles problem (which is NP-complete) but not the same because each subgraphs may contain 2 or 3 edges (unlike the triangles problem, which requires 3 edges in each subgraph).

Is there a polynomial-time algorithm for this problem?

Can a graph be partitioned into vertex disjoint paths of lengths $$3$$?
The problem is shown to be $$\mathsf{NP}$$-hard (see Theorem 1 here).
Note that the proof is given for $$k$$-partition problem. However, it holds for your problem as well. In the proof, the partitions must contain $$3$$ vertices; note the following statement written in the proof: "We claim that $$S'$$ can be partitioned into members of $$C$$ if and only if $$G$$ can be partitioned into $$p = p' + 3q'$$ paths of length at most $$3$$. Since $$|V| = 3p$$, if $$G$$ can be partitioned into $$p$$ paths of length at most $$3$$, then each of these paths must have exactly $$3$$ vertices on it."