GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
149 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)   | 149 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)

1 Answer

+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.5k points)  

Related questions

+2 votes
2 answers
1
asked in Graph Theory by dhingrak Active (1.4k points)   | 305 views
+3 votes
2 answers
2
Top Users Jan 2017
  1. Debashish Deka

    8608 Points

  2. sudsho

    5398 Points

  3. Habibkhan

    4718 Points

  4. Bikram

    4522 Points

  5. Vijay Thakur

    4468 Points

  6. saurabh rai

    4222 Points

  7. Arjun

    4122 Points

  8. santhoshdevulapally

    3742 Points

  9. Sushant Gokhale

    3576 Points

  10. GateSet

    3394 Points

Monthly Topper: Rs. 500 gift card

19,177 questions
24,073 answers
52,975 comments
20,310 users