Different matchings in $K_{10}$, the complete graph with 10 vertices, with 4 edges

139 Views Asked by At

I ran into this graph theory/combinatorics problem, and I'm having some troubles finding the solution.

Considering $K_{10}$, the complete graph with $10$ vertices, what is the number of different matchings in $K_{10}$ with exactly 4 edges? (Two matchings are different if it exists at least one edge that belongs to one matching and not to the other).

1

There are 1 best solutions below

0
On BEST ANSWER

If we differ matchings by their sets of vertices then a number of four-edge matchings of $K_n$ is equal to a number of all eight-vertex subsets of $K_{10}$, that is, as ramseysdream111 noticed, ${10\choose 8}={10\choose 2}=45$. But this doesn’t fit the proposed solution. This solution fits for a natural way to differ graphs (in particular, matchings) on a common set of vertices. Namely, such graphs are equal, if their sets of edges coincide. Given a four-edge matching on $K_10$, there are ${10\choose 2}$ possibilities to pick endvertices for its first edge, ${8\choose 2}$ possibilities to pick endvertices for its second edge, ${6\choose 2}$ possibilities to pick endvertices for its third edge, and ${4\choose 2}$ possibilities to pick endvertices for its third edge. So there are in total $N={10\choose 2}{8\choose 2}{6\choose 2}{4\choose 2}$ possibilities to pick an ordered $4$-tuple of edges of a matching, and so $N/4!$ possibilities to pick an unordered $4$-tuple of edges of a matching.