Matchings in bipartite graph

Question

I was given the following statement: Be $G=(X \cup Y, E)$ a bipartite graph connected with $|X|=|Y|=4$ $|E|=7$ , all maximal matching in G is maximum. I must say if it is true or false and justify. By testing examples I deduced that it is true. But I don't know how I could justify it. All help is welcome! Thank you!

Answer 1

The statement is not true though. You can find maximal matchings that are not maximum matchings.

As a hint: consider a much simpler case, where $|X| = |Y| = 2$ and $|E| = 3$. If you want this to be connected, it must be a path $v_1, v_2, v_3, v_4$ of length three. The set $\{v_2v_3\}$ consisting of only the middle edge is a maximal matching, but not a maximum one (since $\{v_1v_2, v_3v_4\}$ has two edges, it is a maximum matching).

You can scale up this same idea to get a counter-example to your statement.