Alice has a collection of $2m-1$ different perfect matchings of $K_{m,m}$ ($\mathcal{M}_1,\mathcal{M}_2...\mathcal{M}_{2m-1}$). Prove that Alice can pick exactly one edge from each of $\mathcal{M}_{i_1},\mathcal{M}_{i_2},...\mathcal{M}_{i_m}$ for some $\{i_1,i_2,...i_m\}\subset\{1,2,...,2m-1\}$ such that the picked edges form themselves a perfect matching of $K_{m,m}$.
Note: $K_{m,m}$ is the complete bipartite set with $m$ vertices on each side and a perfect matching is a set of edges such that each vertex has degree $1$.
I thought myself and My main idea was to look at subgraphs of $K_{m,m}$, $K_{n,n}$ such that for each $i$, $\mathcal{M}_i$ forms a perfect matching for $K_{n,n}$ and induction would finish the job.
I also thought that interpreting edges as lattice points, but this didn't work.
I would appreciate any help!
What you're looking for is named a "rainbow matching", and its existence is proved in https://www.sciencedirect.com/science/article/pii/S0097316598928941
EDIT : the exact link between these results may not be clear, so check https://en.wikipedia.org/wiki/Rainbow_matching for a more direct explanation :)