Log In
0 votes
Perfect matching is a set of edges such that each vertex appears only once and all vertices appear at least once (EXACTLY one appearance). So for n vertices perfect matching will have n/2 edges and there won't be any perfect matching if n is odd.

I don't know whether i got it properly or not. Can please anybody explain the Perfect matching in a complete graph with simpler examples ?
in Graph Theory 221 views

The confusing part.

Maximal Matching : A matching M of graph ‘G’ is said to maximal if no other edges of ‘G’ can be added to M.

Maximum matching is defined as the maximal matching with maximum number of edges.

Note: Every maximum matching is maximal, but not every maximal matching is a maximum 

1 Answer

2 votes

A perfect matching of a graph is a matching (i.e., an independent edge set) in which every vertex of the graph is incident to exactly one edge of the matching.

 an independent set or stable set is a set of vertices in a graph, no two of which are adjacent.

maximum independent set is an independent set of largest possible size for a given graph G. This size is called the independence number of G, and denoted α(G)


Perfect matching exists for only graph with even number of vertices. No graph with odd number of vertices can contain perfect matching

here u get matching for complete graph


in which every vertex of the graph is incident to exactly one edge of the matching.

Mam, I didn't understood,what u mean by above line. Can you please explain in a more simpler way first please :)

mam please can u answer using an example. Will you? :)
In the reference you provided it is written that perfect matching can also be called as complete matching. But I have read that complete matching is different from perfect matching. Please clear my doubt

Related questions

12 votes
2 answers
Is there a way to find no of perfect matchings in a complete graph Kn where n could be either even or odd..?
asked Dec 2, 2014 in Graph Theory dhingrak 4k views
0 votes
1 answer
When matching number and covering number are same then can we say that it is a perfect matching case?Do i need to check the elements of the set( edges in both matching and covering) also if their cardinality is same?If yes,then can someone give me an example where matching number ... number same but still it is not a perfect match?I am not able to find such a case and i think it will not exist.
asked Jun 8, 2017 in Mathematical Logic rahul sharma 5 363 views