GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
51 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.7k points)   | 51 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.6k points)  
selected by

Related questions

+3 votes
1 answer
1
asked in Graph Theory by Rohan Mundhey Loyal (4.2k points)   | 102 views
+1 vote
2 answers
2
asked in Graph Theory by shikharV Boss (5.2k points)   | 201 views


Top Users Apr 2017
  1. akash.dinkar12

    3514 Points

  2. Divya Bharti

    2546 Points

  3. Deepthi_ts

    2040 Points

  4. rude

    1966 Points

  5. Tesla!

    1768 Points

  6. Shubham Sharma 2

    1610 Points

  7. Debashish Deka

    1588 Points

  8. Arunav Khare

    1454 Points

  9. Kapil

    1424 Points

  10. Arjun

    1420 Points

Monthly Topper: Rs. 500 gift card

22,076 questions
28,042 answers
63,233 comments
24,135 users