The Gateway to Computer Science Excellence
+1 vote
Let G be a graph with no isolated vertices, and let M be a maximum matching of G. For each vertex v not saturated by M, choose an edge incident to v. Let T be the set of all the chosen edges, and let L = M ∪ T. Which of the following option is TRUE?
L is always an edge cover of G.
L is always a minimum edge cover of G.
Both (A) and (B)
Neither (A) nor (B)


Can anyone pls help solving this?

in Graph Theory by | 190 views
option a, right ?
by adding the edges which is incident on the vertices which are not covered in M ==> Making deg(V$_i$) ≥ 1.

it is edge covering, but is it minimum edge covering ? NO, we can't always guarenteed, think why it is NO

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.

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-


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!


Where is the graph?Pic isnt uploaded.!



See this @Ashish Goyal


@Somoshree Datta 5

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! 🙂

But it is mentioned in question that M is a maximum matching..But the matching that u took isnt maximum..

@Somoshree Datta 5

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?

then c is right !

Please log in or register to answer this question.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,375 questions
60,554 answers
95,374 users