Say you had a multigraph G with different coloured lines. You want to decompose it into a collection of single colour 2-vertex graphs all with the same coloured line between the two vertices, by deleting lines from the original multigraph. e.g. a collection of red 2-vertex graphs.
Is there an algorithm to do this in polynomial time (assuming there is only one solution)?
Delete all non-red edges. This takes time $O(V^2)$.
For each surviving red edge, $\{a,b\}$ produce the graph $(\{a,b\},\{\{a,b\}\})$. This takes total time $O(V^2)$.