in Graph Theory
1,463 views
1 vote
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?
A
L is always an edge cover of G.
B
L is always a minimum edge cover of G.
C
Both (A) and (B)
D
Neither (A) nor (B)

 

Can anyone pls help solving this?

in Graph Theory
1.5k views

16 Comments

option a, right ?
0
0
0
0
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
0
0

Can u give a counter example for option B?

0
0

@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)  ??

0
0
edited by

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

0
0

Where is the graph?Pic isnt uploaded.!

 

0
0
0
0

See this @Ashish Goyal

1
1

@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?

0
0

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

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

@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 )

0
0

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

0
0

yes it means to choose one edge among all the edges incident on v..then option c should be correct right?

0
0
then c is right !
0
0

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