edited by
45,136 views
60 votes
60 votes

How many perfect matching are there in a complete graph of $6$ vertices?

  1. $15$
  2. $24$
  3. $30$
  4. $60$
edited by

9 Answers

1 votes
1 votes
For first perfect matching no of options = 5 (we have to choose one vertex, and choose another vertex from remaining 5)
For 2nd  perfect matching no of options = 3 (two vertex are already used)
For third perfect matching no of options = 1( 4 vertex are already used)
total matching = 5 * 3 * 1 = 15
0 votes
0 votes

The Number of Complete Graph is perfect matching is =        (2m)! /  2^m * m !

Where m is postive number

now 6 vertice set to the 2(3)=2(m)   now calcute   6!/8 * 3! = 15 Number Of perfect Matching

 

 

  

0 votes
0 votes

Answer : A

for complete graph(K 2n) , here 2n is no. of vertices

no. of perfect matching = 2n! / ((2^n) * (n!) )

sono. of perfect matching = 6! / (2^3 * 3!) = 720 / (8 * 6) = 15

0 votes
0 votes
For perfect matching the number of edges to be selected such that no two edge are adjacent to each other.

Hence number of ways to select the edges in complete graph with 6 vertices =  6∁2 * 4∁2 * 2∁2

Now for the set of edges selected the ordering isn’t important,  hence    6∁2 * 4∁2 * 2∁2  /3!

answer is 15    option A
Answer:

Related questions

65 votes
65 votes
9 answers
1
Kathleen asked Sep 17, 2014
15,496 views
A graph $G=(V,E)$ satisfies $\mid E \mid \leq 3 \mid V \mid - 6$. The min-degree of $G$ is defined as $\min_{v\in V}\left\{ \text{degree }(v)\right \}$. Therefore, min-d...
65 votes
65 votes
5 answers
2
3 votes
3 votes
0 answers
3
admin asked Dec 15, 2022
372 views
Count the number of perfect matchings in the bipartite graph whose adjacency matrix $\text{A}$ is as follows.\[\left[\begin{array}{lll}1 & 1 & 0 \\0 & 1 & 1 \\1 & 1 & 1\e...
4 votes
4 votes
2 answers
4