Register

GATE CSE 2003 | Question: 36

• edited by
50,386 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
User Avatar

10 Answers

2 votes
2 votes

No. of perfect matchings in a complete graph $K_{2n}$ = 

$$\frac{(2n)!}{n! 2^n}$$

Please note it is for $K_{2n}$ and not $K_{n}$.

 

Here, 2n = 6.

So, $\frac{6*5*4*3*2}{3*2*8}=15$

As for Cyclic graphs $C_n$

Two matchings if n is even, none otherwise.

Sources: https://math.stackexchange.com/questions/60894/how-to-find-the-number-of-perfect-matchings-in-complete-graphs

https://math.stackexchange.com/questions/1981111/number-of-distinct-perfect-matchings-in-a-cycle

User Avatar
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
User Avatar
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

 

 

  

User Avatar
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!) )

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

User Avatar
Page:
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

65 votes
65 votes
9 answers
5
Kathleen asked Sep 17, 2014
15,635 views
GATE CSE 2003 | Question: 40
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-degree of $G$ cannot be $3$ $4$ $5$ $6$
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...
User Avatar
65 votes
65 votes
5 answers
6
Kathleen asked Sep 16, 2014
15,376 views
GATE CSE 2003 | Question: 8, ISRO2009-53
Let $\text{G}$ be an arbitrary graph with $n$ nodes and $k$ components. If a vertex is removed from $\text{G}$, the number of components in the resultant graph must necessarily lie down between $k$ and $n$ $k-1$ and $k+1$ $k-1$ and $n-1$ $k+1$ and $n-k$
Let $\text{G}$ be an arbitrary graph with $n$ nodes and $k$ components. If a vertex is removed from $\text{G}$, the number of components in the resultant graph must neces...
User Avatar
3 votes
3 votes
0 answers
7
admin asked Dec 15, 2022
384 views
DRDO CSE 2022 Paper 1 | Question: 9
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 \end{array}\right]\]
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...
User Avatar
4 votes
4 votes
2 answers
8
admin asked Sep 1, 2022
961 views
TIFR CSE 2022 | Part B | Question: 2
Let $G=(V, E)$ be an undirected simple graph. A subset $M \subseteq E$ is a matching in $G$ if distinct edges in $M$ do not share a vertex. A matching is maximal if no strict superset of $M$ is a matching. How many maximal matchings does the following graph have? $1$ $2$ $3$ $4$ $5$
Let $G=(V, E)$ be an undirected simple graph. A subset $M \subseteq E$ is a matching in $G$ if distinct edges in $M$ do not share a vertex. A matching is maximal if no st...
User Avatar
Link Copied!