Consider a bipartite graph (does not have to be complete) $G$ with vertex parts $A$ and $B$ of equal size, where each vertex has a preference order on its neighbors. Show that each of $A$ and $B$ can be partitioned into two parts such that one consists of vertices that is contained in all stable matchings and the other consists of vertices that is never contained in any stable matching.

Proof) By definition, a matching $M$ is not a stable matching iff there exists $(u,v) \in M^c \cap E$ such that $u>_v M(v)$ and $v>_u M(u)$.
A matching $M$ is a stable matching iff for all $(u,v) \in M^c \cap E$, $M(u) > _v u $ or $M(u) >_u v$.
Let define $M(v)$ for a vertex $v$ be a vertex such that $v M(v) \in M$ if $v$ is contained in $M$.
Suppose that there are $a_1 \in A$ and stable matching $M_1$ and $M_2$ such that $a_1 M_1 (a_1) \in M_1$ and $a_1 M_1(a_1) \notin M_2$.
Let $b_1:=M_1(a_1)$.
Since $M_2$ is stable matching $M_2(b_1) >_{b_1} a_1$.
That is $b_1$ is contained in $M_2$.
Let $a_2 := M_2 (b_1)$.
Since $M_1$ is stable matching and $a_1b_1\in M$, $M_1(a_2) >_{a_2} b_1$.
Let $b_2:=M_1(a_2)$.
Continuing this process two sequence $a_i\in A$ and $b_i \in B$ are obtained such that $a_i \neq a_j$ and $b_i\neq b_j$ for all $i,j$ satisfying $i\neq j$.
However, it is impossible because $G$ is finite.
So, for all $a\in A$ either $a$ is contained in all stable matching or $a$ is never contained in any stable matching.
For the all elements $b \in B$, these property holds.