GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
48 views
what is the matching number of $K_{2,3}$ graph.and also explain matching number of $K_{m,n}$(simplification).
asked in Graph Theory by Veteran (10.6k points)   | 48 views

1 Answer

+5 votes
Best answer

Matching number of a graph is defined as the maximum number of non-adjacent edges in a graph.

(I have marked one maximum-possible set of non-adjacent edges, but other set is also possible)

In a complete bipartite graph $K_{m,n}$ $m$ nodes are adjacent to each of the $n$ nodes and $n$ nodes are adjacent to each of $m$ nodes. (basic definition of bipartite graph)

So, If an edge is to be included in counting of Matching number, then all adjacent edges cannot be included. 

So, Matching Number in $K_{2,3} = 2$ and in $K_{3,3} = 3$

Although there may exist a much formal proof, but by taking few more examples it can be said that Matching Number for $\color{maroon}{K_{m,n} = \;min(m,n)}$

answered by Veteran (24.1k points)  
selected by

Related questions

+3 votes
1 answer
1
asked in Graph Theory by Rohan Mundhey Loyal (4.2k points)   | 94 views
+1 vote
2 answers
2
asked in Graph Theory by shikharV Boss (5.1k points)   | 178 views
Members at the site
Top Users Feb 2017
  1. Arjun

    4676 Points

  2. Bikram

    4004 Points

  3. Habibkhan

    3738 Points

  4. Aboveallplayer

    2966 Points

  5. sriv_shubham

    2278 Points

  6. Smriti012

    2212 Points

  7. Arnabi

    1814 Points

  8. Debashish Deka

    1788 Points

  9. sh!va

    1444 Points

  10. mcjoshi

    1444 Points

Monthly Topper: Rs. 500 gift card

20,788 questions
25,938 answers
59,532 comments
21,923 users