What if number of vertices is an ODD number?

Dark Mode

Parshu gate
asked
in Graph Theory
Nov 6, 2017

1,916 views
4 votes

Best answer

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

4

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.