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

Related questions

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


Top Users Aug 2017
  1. ABKUNDAN

    4670 Points

  2. Bikram

    4556 Points

  3. akash.dinkar12

    3420 Points

  4. rahul sharma 5

    3124 Points

  5. manu00x

    2864 Points

  6. makhdoom ghaya

    2450 Points

  7. just_bhavana

    2136 Points

  8. Tesla!

    2042 Points

  9. stblue

    1930 Points

  10. joshi_nitish

    1686 Points


24,970 questions
32,072 answers
74,567 comments
30,150 users