edited by
2,223 views
7 votes
7 votes

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

edited by

2 Answers

2 votes
2 votes

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 

1 votes
1 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.

Related questions

16 votes
16 votes
2 answers
2
dhingrak asked Dec 2, 2014
10,619 views
Is there a way to find no of perfect matchings in a complete graph Kn where n could be either even or odd..?
0 votes
0 votes
1 answer
3
atul_21 asked Dec 21, 2017
509 views
I am not convinced by this. Please explain or please tell me the source from where I can clear this out.