GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
195 views

Given explanation:

In the above explanation, it is written that matching number is 4 but I am getting matching number as 3 for this graph(choosing edges 1-2, 3-4 and 6-7). Please check where I am going wrong

asked in Graph Theory by Boss (5.1k points)   | 195 views
You are calculating edge covering number.

Matching number : 4 (1-2,3-4,5-6,8-7)
Thanks!
I think edge cover is also 4.. 1-2 3-4 6-7 is not covering verter #8..
matching number-4

it can also be

(3-4)(2-5)(1-6)(8-7)

2 Answers

+1 vote

In Matching graph no 2 edges are adjacent it means the degree of vertex is 1

So we find such vertices and edges 

Let us start with 2 then we get (2-1),(3-8),(4-7),(5-6) these edges are matching so the matched number is  4 

Even these edges (2-3),(1-8),(4-5),(7-6) are matching so the matched number is  4 

These edges (2-5),(3-4),(1-6),(8-7) are matching so the matched number is  4 

By choosing these edges we could have vertices with 1 degree 

answered by Veteran (13.7k points)  
0 votes
option a is true matching number is 4 ,( 12 , 38, 47,56)

option b is also true  because it is bipartite graph .

option c is true as matching covers every vertex.

option d is not true . It is not complete bipartite.
answered by Junior (989 points)  

Related questions

+2 votes
2 answers
1
asked in Graph Theory by dhingrak Active (1.4k points)   | 479 views
+3 votes
2 answers
2


Top Users Mar 2017
  1. rude

    4272 Points

  2. sh!va

    2994 Points

  3. Rahul Jain25

    2804 Points

  4. Kapil

    2608 Points

  5. Debashish Deka

    2244 Points

  6. 2018

    1414 Points

  7. Vignesh Sekar

    1338 Points

  8. Akriti sood

    1246 Points

  9. Bikram

    1246 Points

  10. Sanjay Sharma

    1016 Points

Monthly Topper: Rs. 500 gift card

21,452 questions
26,771 answers
60,972 comments
22,985 users