title: Worst Case for stable matchings
body: <p>In the stable matching problem, I am trying to generate the preference lists for worst case.I came across a paper that says this is the worst case for n=5</p>
  
  <pre><code>m1: w1 w2 w3 w4 w5
  m2: w2 w3 w4 w1 w5
  m3: w3 w4 w1 w2 w5
  m4: w4 w1 w2 w3 w5
  m5: w1 w2 w3 w4 w5
  
  w1: m2 m3 m4 m5 m1
  w2: m3 m4 m5 m1 m2
  w3: m4 m5 m1 m2 m3
  w4: m5 m1 m2 m3 m4
  w5: m1 m2 m3 m4 m5
  </code></pre>
  
  <p>Intuitively, this kind of makes sense.But can anyone formally argue why this is the worst case and why we cannot get a worse case than that?</p>