retagged by
397 views

1 Answer

Best answer
6 votes
6 votes

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)}$

selected by

Related questions

0 votes
0 votes
1 answer
1
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.
7 votes
7 votes
2 answers
4
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)....