GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
201 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.2k points)   | 201 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 Active (1.1k points)  

Related questions

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


Top Users Apr 2017
  1. akash.dinkar12

    3660 Points

  2. Divya Bharti

    2580 Points

  3. Deepthi_ts

    2040 Points

  4. rude

    1966 Points

  5. Tesla!

    1768 Points

  6. Debashish Deka

    1614 Points

  7. Shubham Sharma 2

    1610 Points

  8. Prashant.

    1492 Points

  9. Arjun

    1472 Points

  10. Arunav Khare

    1464 Points

Monthly Topper: Rs. 500 gift card

22,086 questions
28,063 answers
63,297 comments
24,169 users