659 views

Find the matching number for the given graph-

Matching  it 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 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

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.

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

by