There are $n$ men and $n$ women. Each man has a preference list of the women he wants to marry, and each women also has a preference list of her ideal men. The problem is that how should we match these people such that there is no instability in the result.
Here, instability means that suppose there are two matches in the result: $(m,w)$ & $(m',w')$, however, if $m$ prefers $w'$ over $w$ and simultaneously $w'$ also prefers $m$ to $m'$, then this is called a instable match. (i.e. A man and a woman who are not matched together prefer each other to their current matches)
The propose algorithm: While some men are still single, then each single man proposes to his next favorite woman, at the same time, each woman rejects all but her top suitor to whom she tentatively says "yes".
Theorem 1 This algorithm will terminate in $n^2$ time.
Proof: In each iteration, a man proposes to a woman he hasn't talked to yet. There are $n^2$ possible proposals, so there are at most $n^2$ iterations.
Theorem 2 The matching result is stable.
Proof (By contradiction): Suppose it is NOT stable. Given the matching result $(m,w)$ & $(m',w')$, since it is instable, we can tell that $m$ prefers $w'$ to $w$, and $w'$ prefers $m$ over $m'$. Since $m$ prefers $w'$ to $w$, he must have proposed to $w'$ earlier and then got rejected. Therefore, here comes a contradiction that if $m$ gets rejected by $w'$, then it means $w'$ has a better choice than $m$, which is contradicted to the assumption of instability (according to the assumption $w'$ should prefer $m$ but not reject him).
Is it possible to a man to be rejected by everyone? No, because there are $n$ men and $n$ women, once a woman is tentatively matched and then the outcome of her never gets worse (worst case is single). Since each man can propose to every woman, so there must be a woman who will accept him.
Theorem 3 All possible executions of this algorithm yield the same stable matching, and in this stable matching, all men are simultaneously matched to their best possible mate.
Proof (By contradiction): Suppose there exist another stable matching $S'$ such that certain man is matched with someone other than his best mate. Since men propose in decreasing order of preference, so some man is rejected by a valid partner.
In $S'$, let $m$ be such man, and $w$ be the first valid woman who rejects him. (Which means $w$ actually is $m$'s best valid match, but we suppose she somehow rejects the man). Besides, let $S$ be a stable matching where $m$ and $w$ are matched, while $m'$ and $w'$ are matched.
In building $S'$, when $m$ is rejected by $w$ in favor of $m'$. We can say that $w$ prefers $m'$ over $m$. Moreover, $m'$ is not rejected by any valid partner at the point when $m$ is rejected by $w$, thus, $m'$ prefers $w$ to $w'$. (The reason $m'$ must prefer $w$ because he has to force $w$ reject $m$, so $m'$ must also propose to $w$ first.) As a result $m',w$ is not stable in $S$, which is the contradiction.
Theorem 4 All women are simultaneously matched to their worst possible mate.
Proof (By contradiction): Suppose there exists a stable matching $S$ where $m$ and $w$ are matched. And there is another matching $S'$ where $m$ and $w'$ matches, but $m$ is not the worst valid partner for $w'$ (i.e. $w'$ prefer $m$ to $m'$). In $S'$, $m$ is paired with $w'$, so according to man's optimality in $S'$ $w'$ is $m$'s best possible choice (i.e. $m$ also prefer $w'$ to $w$). However, this shows a instability in $S$, which is the contradiction.
Acknowledgement:
This article is my learning notes of course CS331 Algorithms and Complexity (Spring 2014), lectured by Prof. Greg Plaxton.