Invariant for Gale–Shapley algorithm (Mating Ritual Algorithm)? I found the following invariant for Mating Ritual algorithm (Lehman, Leighton and Meyer, Mathematics for Computer Science, §6.4) while going through MIT reading material:

Definition. Let $P$ be the predicate: For every woman, $w$, and
  every man, $m$, if $w$ is crossed off $m$’s list, then $w$ has a suitor whom
  she prefers over $m$.   
Lemma: $P$ is an invariant for The Mating
  Ritual. 
Proof. By induction on the number of days.
Base Case: In the beginning (that is, at the end of day 0), every woman is on  every
  list-no one has been crossed off and so $P$ is vacuously true.
Inductive Step: Assume $P$ is true at the end of day $d$ and let $w$ be a woman that
  has been crossed off a man $m$’s list by the end of day $d + 1$.
  Case 1: $w$ was crossed off $m$’s list on day $d + 1$. Then,$w$ must have a suitor she
  prefers on day $d + 1$.
  Case 2: $w$ was crossed off $m$’s list prior to day
  $d + 1$. Since $P$ is true at the end of day $d$, this means that $w$ has a
  suitor she prefers to $m$ on day $d$. She therefore has the same suitor or
  someone she prefers better at the end of day $d + 1$.   
In both cases, P is true at the end of day $d + 1$ and so $P$ must be an invariant

I am unable to understand why the author is considering the Case 2.
In the inductive step first we are assuming the following:

"let $w$ be a woman that has been crossed off a man $m$’s list by the end
  of day $d + 1$"

And then later in Case 2, We are considering the possibility of $w$ being crossed of the day prior to $d+1$. I find it contradictory. 
Could you please me understand ?
 A: We want to show that at any point in the algorithm, if it's true that $m$ has crossed off $w$'s name from his list at some point in the past, then $w$ has a suitor she likes better than $m$.
So the assumption at the beginning of the inductive step is simply describing the situation at the end of day $d+1$: we assume that, at this point in the algorithm, $w$'s name appears on $m$'s list with a line through it.
Then the two cases are considering different possibilities for when the crossing out occurred:


*

*The current day, day $d+1$, is in fact the day that $w$'s name got crossed out. Then, we should look at how this happened: $w$'s name gets crossed out because she rejects $m$, and $w$ rejects $m$ because she has met a better suitor $m'$.

*Actually, $w$'s name got crossed out on a previous day (and stays crossed out on day $d+1$, because once a name is crossed out, it stays crossed out forever). In this case, the inductive hypothesis applies, and you have the rest of the proof there.

