Graph theory

Question

Comments

@Pawan,

12 is correct answer, see how.

it is well known for any graph that matching no. + edge cover = no. of vertices

edge cover-> min no. of edges to cover all the vertices.

for K₂₅, with 12 edges we can cover max. of 24 vertices, and one more edge needed to cover 25th vertex,

so edge cover = 12+1 = 13,

now matching no. = no. of vertices - edge cover = 25 - 13 = 12.

i think you are confusing yourself with no. perfect matching which is '0' for K2n+1(i.e complete grah with odd no. of vertices), but here in qsn it is asked just a matching no. not a perfect matching

---

Great !!! @nitish _/\_

---

     joshi_nitish Sir....a heartily thanks .... :) 

Answer 1

matching number =   floor (no of vertices / 2).

In this case, floor (25/2) = 12

Comments

can u explain how ?

---

Matching Number is the no of edges in maximal matching. So, There will be 24 vertices can be matched with 12 edges but one remains unmatched.

---

I think the matching number is asked not the perfect matching number. You are talking about perfect matching.

https://www.geeksforgeeks.org/mathematics-matching-graph-theory/

Answer 2

Yes it should be 12 only.

Floor(25/2)=12