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.

  • $\begingroup$ Alternatively, pick $3$ of the deleted edges and pick one vertex from each edge, so $\binom63\cdot2^3=160$. $\endgroup$ – bof Jul 9 '14 at 1:20
  • $\begingroup$ @bof Nicely done! $\endgroup$ – Peter Woolfitt Jul 9 '14 at 2:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.