How to prove this Lemma?

Explicit/Algorithmic This way involves just explaining what the family is in plain words or algorithmically, like pseudo-code. For our problem, our family has two groups, M (men) and W (women), each containing mi and wi such that 0w2>>wn1>wn - m2:w2>w3>>wn>w1 - - mn:wn>w1>>wn2>wn1 Women - w1:m2>m3>>mn>m1 - w2:m3>m4>>m1>m2 - - wn:m1>m2>>mn1>mn Now with this family, we want to show there are at least n stable matchings. So how can we prove that this family satisfies this? Well this is where working with a family of inputs nelps, as we can find some property of this input that is repeatable and helps prove there are at least n stable matches. In this case, we will help prove this be outlining a lemma which you will then prove for your proof of correctness). Proof Idea Let's say that for our stable matching, let's consider an input of size 4(n=4). This gives us preference lists as follows: In these charts, the person whose preference list we are referencing is noted on the left side, followed by their preference list in order of most preferred to least preferred. One stable matching we can consider is if all of the men get their most preferred choice. Looking at the preference lists as a grid, we notice that matching each man with their most preferred choice means all of their matches are in column 1 , and the corresponding matches for the women are in column 4. This is the other way around if the women get their most preferred choices - their choices are in their column 1 , and the men's are in column 4 . Now imagine the men all get their second most preferred woman. That is, m1 to w2,m2 to w3, etc. This puts all of their matches in column 2 in their lists, and in the women's list, the men are all in column 3. We can expand this further if we would like, but we are already noticing a trend. That is, for a given stable matching, the matches represent some column i in one list, and column ni+1 in the other. We can present this as a lemma: Lemma If you match one group with their preferences in a specific column i, then the other group is matched with their preferences in column ni+1