retagged by
2,709 views
4 votes
4 votes

retagged by

1 Answer

Best answer
4 votes
4 votes

a) To find the chromatic number of a graph we should look for the maximum sized clique i.e. a subgraph of a graph which is complete and contains maximum no of vertices i.e. contains K3 , K4 , Ketc.So we can see that the maximal clique in the above graph is 3 . So 3 colours are sufficient to colour the entire graph such that no two adjacent vertices get same colour.Hence chromatic number of the given graph = 3.

b) Matching number is the set of maximal no of non intersecting edges.So here we can take (f,g) , (h,a) , (d,b) , (e,c) which are not intersecting with each other.Hence matching no = 4

Hence chromatic + matching no = 3 + 4 = 7

Hence , B) should be the correct option.

selected by
Answer:

Related questions

7 votes
7 votes
2 answers
1
shikharV asked Jan 18, 2016
2,223 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)....
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..?
1 votes
1 votes
1 answer
3
ashish pal asked Jan 20, 2018
479 views
my answer is Cbut the answer given is Asomeone please explain
0 votes
0 votes
1 answer
4
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.