The Gateway to Computer Science Excellence
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 by Loyal (6.9k points) | 138 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

+1 vote

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

by Veteran (117k points)

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
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,645 questions
56,601 answers
102,230 users