Every Stable Marriage problem has at least one solution. However, how to know the largest number of solutions to a stable marriage problem? The Gale-Shapley algorithm can only find one man-optimal solution. If we use woman-optimal method to run Gale-Shapley, there may be another solution. Are there at most two solutions to an instance of stable marriage, or can Gale-Shapley only find two solutions, and there are some other solutions beyond them?
See https://cstheory.stackexchange.com/questions/5619/what-is-the-maximum-number-of-stable-marriages-for-an-instance-of-the-stable-mar where it is discussed that an exponential worst-case lower bound of Omega(2.28^n) stable marriages is given for all n for n men/women (by giving a family of examples where this many stable marriages are possible).