Dark Mode

659 views

8 votes

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

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

2 votes

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.