I try to find a bipartite graph where no maximum size matching is stable, but am kind of confused with that question. I already proved with the Gale-Shapley algorithm that every bipartite graph has a stable matching. However regarding the question, I don't quite understand what they mean with the maximum size matching and how this is linked to stableness. Could anybody explain it to me by means of an example graph?
Thanks for your help.
The Gale-Shapley algorithm is talking about stable matchings in the complete bipartite graph, where anyone on one side can be matched to anyone on the other side.
In general, you can take any bipartite graph, give each vertex preferences over its neighbors, and try to find a stable matching. In this case, some edges from one side to the other might not exist: those vertices cannot be matched to each other, no matter what anyone's preferences are.
Rather than solve the problem for you, I'll suggest a graph to try this with: the $6$-cycle. This has two matchings of size $3$, and you should think about how to assign the preferences so that neither of those matchings is stable.
(This doesn't contradict Gale-Shapley because Gale-Shapley would want to pick one of the other matchings that don't exist in this graph, but do exist in the complete bipartite graph $K_{3,3}$.)