in Graph Theory recategorized by
373 views
1 vote
1 vote

is there any easy way to do this i did it by making equation,Mn+Ec=Vn,  Vc+In=Vn

in Graph Theory recategorized by
373 views

1 Answer

1 vote
1 vote
let matching number=M , independence number=N , edge cover number=E, vertex cover number =V

given that V-E=2k  , M*I=1-2k  ----(1)

and we know that V+I=n and M+E=n  (n=number of vertices)

                                          V-E=M-I=2k  ---(2)

     we need M+I

                so we know that-- (a+b)^2=(a-b)^2+4ab

                                            (M+I)^2=(M-I)^2+4MI

                                                             from eq(1)and (2)  (M+I)^2 =  4k^2+4(1-2k)

                                                                                                      =4(k^2-2k+1)

                                                                                                          =4(k-1)^2

                                                                                        so M+I= 2(k-1)