The Gateway to Computer Science Excellence
+1 vote
587 views

in Graph Theory by Active (3.1k points) | 587 views

2 Answers

+4 votes
Best answer

Number of perfect matching in complete graph $K_{2n}= \frac{2n!}{2^{n}n!}=(2n-1)(2n-3)(2n-5)....1$

For $K_{4}= \frac{4!}{2^{2}2!}=3$

3 is the correct answer

by Boss (15.6k points)
selected by
0
Can u explain what a perfect matching is?

What if number of vertices is an ODD number?
+3

Perfect matching of a graph is a matching in which degree of each vertex is exactly one.

Why it is not possible for ODD number of vertices ? I think we can prove it by handshaking lemma, we know that $\sum degree of vertices = 2* edges$

Since each vertex has exactly degree 1

we can write as $1*\left | V \right |=2*\left | E \right | \\ \left | E \right |=\frac{\left | V \right |}{\left | 2 \right |}$

It shows number of vertices must be even as edges should be a positive integer , hence number of vertices cannot be ODD.

For K4 no. of perfect matching  are

+2 votes

Matching in a graph is Distinct set of edges.

 matching M in G is a set of pairwise non-adjacent edges; that is, no two edges share a common vertex

Types of Maching

1.Maximum:-Contain maximum no. of edges

2.Maximal:-A set when no. more edges can  be added

3.Complete matching from set v1 to set v2 such that every vertex in v1 gets matched

4.Perfect Matching :-

1.when every vertex gets matched

2.perfect matching is only possible with even number of vertices

3.No. of perfect matchings for odd number of vertices are 0.

4.No. of matching in complete graph with even number of vertices are 

(2n)!/(2^n) *(n!)

or

(2m-1) *(2m-3)*(2m-5)....1

here, n=2m=number of vertices.

by Active (4.7k points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,647 questions
56,508 answers
195,530 comments
100,964 users