Register

GATE CSE 2003 | Question: 36

• edited by
50,379 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

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

Perfect matching of 1-factor means that edges have to be selected such that no two edges have same vertices and all the vertices have to be covered in the perfect matching set. 

Hence, for the given question, there can be 6C2 *  4C2 * 2C2 = 90     Now, the three pairs selected have the same order, hence 90/3! = 15. So option A is the answer

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
9
Kathleen asked Sep 17, 2014
15,634 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
10
Kathleen asked Sep 16, 2014
15,373 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
11
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
12
admin asked Sep 1, 2022
960 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!