Virtual Gate Test Series: Discrete Mathematics - Graph Theory (Matching Number)

Question

Find the matching number for the given graph-

Answer 1

Matching means that no 2 edges are adjacent simply a vertex with degree 1

if we have a vertex with degree 0 we say not matched.

In the above graph if we start with G we have 2 edges for G In matching we consider 1 edge since if both are considered we get the degree of G as 2 so if we consider G-A edge then node 2 is alone and has degree 0 it makes graph to be not matched so we consider G-2 edge, A-0 edge  T has edges with 0 and 1 since A-0 edge is present if we consider 0 then degree of 0 is 2 so we don't consider

we have T-1 edge then we are left with edge E-6

Totally we get (G-2),(A-0),(T-1),(E-6) so matching number is 4

Answer 2

The matching number  of graph , sometimes known as the edge independence number, is the size of a maximum independent edge set.

and maximum means max beween the minimal independence edge sets,which we can form from the graph.So here  

maximum independent edge set is { (G,2) , (A,0) , (T,1) , (E,6) } hence ans is 4.

Answer 3

Matching number means the  maximum independent set of edges i.e. maximum number of edges taken such that no two edges have same common vertex. Hence answer is 4