Ace workbook: If G is a complete bipartite graph with n vertices (n >= 2) and minimum number of edges, then matching number of G is ____ closed

Question

If G is a complete bipartite graph with n vertices (n >= 2) and minimum number of edges, then matching number of G is ____

• A. 1
• B. n-1
• C. ⌊n/2⌋
• D. ⌈n/2⌉

Answer 1

 

Matching number of G  = number of edges in maximum matching of G.

 

complete bipartite graph is a graph where vertices of graph is divided into two groups such that each vertex of one group is associated with each vertex of another group but not with any vertex of same group.

 

given that G is complete bipartite graph with n>=2 and min number of edges.

so to get min no. of edges in complete bipartite graph with n vertices one group will have (n-1) vertices and other group will have only 1 vertices then number of edges is n-1 which is min than any other complete bipartite graph with n vertices.

so we can see every such complete bipartite graph with min edges and n>=2 will have matching number as 1 always

 

Comments

Thank you explaining !

Answer 2

In a complete bipartite graph with n vertices (n ≥ 2) and the minimum number of edges, the matching number (also known as the maximum matching size) of G is equal to the size of the smaller partition.

 

Let's denote the two partitions of the complete bipartite graph as A and B, with |A| = a and |B| = b, such that a + b = n. The minimum number of edges occurs when each vertex in A is matched with a unique vertex in B, and there are no other edges in the graph.

 

In this scenario, the matching size is the size of the smaller partition, which is min(a, b). So, the matching number of G is min(|A|, |B|) or equivalently, min(a, b).