Let G(A,B,E) a bipartite graph with a maximum size matching of t. We start const
ID: 3209676 • Letter: L
Question
Let G(A,B,E) a bipartite graph with a maximum size matching of t. We start constructing a matching "greedily" by taking and edge, then taking another, and so on, such that the newly chosen edges cannot share a vertex with a previously taken one. We stop when no such edge is available. This algorithm clearly generates a matching. Show that the size of this matching is at least t/2 (floor, if t is odd).
NOTE: DO NOT PRESENT A SMALL CASE EXAMPLE AND CLAIM IT AS A PROOF! YOU NEED TO PROVIDE A PROOF FOR AN ARBITRARY GRAPH!
Explanation / Answer
A matching in a Bipartite Graph is a set of the edges chosen in such a way that no two edges share an endpoint.
Given that
G(A,B,E) is a bipartite graph with a maximum size matching of t. We start constructing a matching "greedily" by taking and edge, then taking another, and so on, such that the newly chosen edges cannot share a vertex with a previously taken one. We stop when no such edge is available.
WE can prove by induction.
First let us have vertices =3
Then we can have maximum size matching is 2, one connecting 1 and 2 vertex and other one connecting any other pair namely 1,3 or 2,3. Thus there are 2 sizes max matching which is greater than 3/2
Thus true for vertex =3
Let us assume this statement is true for number of vertices n =2k+1
i.e. maximum matching size is > (2k+1)/2 = k+1
In 2k+1, vertices k edges would connect pairwise 2k vertices, while the last edge is for the remaining one.
Add two more vertices to the graph.
To connect those two vertices, we can use one edge and this will give max matching size as k+1+1 =k+2
i.e. For 2k+3 vertices max matching size >=(2k+3+1)/2
If true for 2k+1, it is true for 2k+3.
When k =1, we had 3 vertices and it was true.
hence by induction true for all 2k+1 form i.e. all odd natural numbers.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.