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

Related questions

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


Top Users May 2017
  1. akash.dinkar12

    3308 Points

  2. pawan kumarln

    1884 Points

  3. Bikram

    1656 Points

  4. sh!va

    1640 Points

  5. Arjun

    1396 Points

  6. Devshree Dubey

    1272 Points

  7. Debashish Deka

    1162 Points

  8. Angkit

    1048 Points

  9. LeenSharma

    1010 Points

  10. Arunav Khare

    754 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 May 22 - 28
  1. Bikram

    742 Points

  2. pawan kumarln

    510 Points

  3. Arnab Bhadra

    490 Points

  4. bharti

    304 Points

  5. LeenSharma

    248 Points


22,832 questions
29,157 answers
65,233 comments
27,673 users