Partition into Triangles

Input

Graph $G = (V,E)$ with $|V| = 3q$ for some integer $q$.

Question

Can the vertices of $G$ be partitioned into $q$ disjoint sets $V_1, V_2, \dots, V_q$, each containing exactly 3 vertices, such that for each $V_i = \{u_i, v_i, w_i\}$, $1 \leq i \leq q$, all three of the edges $\{u_i, v_i\}$, $\{u_i, w_i\}$, and $\{v_i, w_i\}$ belong to $E$?

Classes

• NP-complete

Comments

See Partition into Isomorphic Subgraphs for a generalization.

Proofs

NP-complete

Transformation from 3-Dimensional Matching.

Reducible from

• 3-Dimensional Matching