Can anyone pls help solving this?
@Shaik Masthan how?
Shaik Masthan
Can u give a counter example for option B?
@Shaik Masthan, @Somoshree Datta 5, @Shubhanshu
Given answer is C. I was also thinking A. It would not result in min. edge cover right?
The explanation given by them is-
Both statements are true. (A) This construction of L is exactly the one in the proof of a theorem. L is an edge cover by construction, since all edges not saturated by M are covered by the additional edges T; and it is a minimum one because its size is n−|M| = n−α'(G) = β'(G) by the theorem. For option (B), it has no superfluous edges that can be removed from it and still have a edge cover, but this does not prove that L is minimum. Option (C) is correct choice.
Both statements are true. (A) This construction of L is exactly the one in the proof of a theorem. L is an edge cover by construction, since all edges not saturated by M are covered by the additional edges T; and it is a minimum one because its size is
n−|M| = n−α'(G) = β'(G)
by the theorem. For option (B), it has no superfluous edges that can be removed from it and still have a edge cover, but this does not prove that L is minimum. Option (C) is correct choice.
I am not able to understand this. they are saying it is minimum in (A). And then in (B) they say "this does not prove that L is minimum".
Is anyone getting what they are trying to explain through this-
n−|M| = n−α'(G) = β'(G) ??
@Somoshree Datta 5
Counter Example-
G:
This is having a maximum matching, since no more edges can be added.
Now |T| = 4 edges.
and, |L| = |M U T| = 5 edges.
But the minimum edge cover of G will have 4 edges. So L is not minimum.
Minimum Edge Cover of G:
Pls correct if i am wrong!
Ashish Goyal
Where is the graph?Pic isnt uploaded.!
Edited!
See this @Ashish Goyal
It is just a particular case for which L would be minimum. And there would be many such cases. But Can we say that L is always the minimum edge cover?
I have shown you a counter example for this where L is not the minimum.
So is B true? Did I went wrong somewhere?
Thanks @Somoshree Datta 5, @Shaik Masthan, @Shubhanshu s
I got it now. I was confused with the maximal matching and maximum matching!
Now, It's clear. The example which i gave had maximal matching and not maximum matching!
The maximum matching will have minimum edge cover.
Thanks a lot! 🙂
can you check this ? ( i am not getting where i am doing the mistake ! even i am not getting the explanation of answer provided by them )
choose an edge incident to v. Let T be the set of all the chosen edges,
is it mean, only choose one among all edges which are incident on v ?
if yes, then option C is correct !
Unfortunately i am thinking NO
yes it means to choose one edge among all the edges incident on v..then option c should be correct right?
64.3k questions
77.9k answers
244k comments
80.0k users