Perfect Matching Combination Problem

We know:

A perfect matching (a.k.a. 1-factor) is a matching which matches all vertices of the graph.

if we remove edges of perfect matching of a 12-Complete Graph. how many triangle remain in this graph?

Every set of three vertices forms a triangle in $K_{12}$, so before the removal, we have $\binom{12}{3}=220$ triangles. Removing a single edge destroys $\binom{10}{1}=10$ triangles (we just choose the last vertex that would have been in the triangle). Since we delete a perfect matching, no two edges we delete lie in the same triangle in $K_{12}$. We delete $6$ edges. This gives us a total of $220-(6)10=160$ triangles remaining.
• Alternatively, pick $3$ of the deleted edges and pick one vertex from each edge, so $\binom63\cdot2^3=160$. – bof Jul 9 '14 at 1:20