## 3 The Easy Cases
Now, in the proof of Theorem 1, we argued that when \(f_{1},w_{1},f_{2},w_{2},\ldots,f_{k},w_{k}\) forms a \(\hat{\mu}\)-alternating path and \(w_{1},w_{2},\ldots,w_{k}\) is a path in \(G\), a contradiction arises. Thus, at least one of the edges \(w_{1}w_{2}\), \(w_{2}w_{3},\ldots,w_{k-1}w_{k}\) must be missing from \(G\) and therefore present in \(\bar{G}\). If \(\hat{\mu}\bigoplus\mu\) has \(x\)\(\hat{\mu}\)-alternating paths, \(\bar{G}\) has at least \(x\) pairwise vertex-disjoint edges. Since \(x\leq r\), \(|\hat{\mu}|-|\mu|\leq r\). Now suppose some firms in \(I\) have capacity greater than \(1\). Again, construct the HR+SN instance \((I^{(1)},G)\) from \((I,G)\). Since \(\hat{\mu}\) is a maximum locally stable matching of \((I,G)\), \(\hat{\mu}^{(1)}\) is a locally stable matching of \((I^{(1)},G)\), but it may not be the largest such matching. Let \(\tau\) be a maximum locally stable matching of \((I^{(1)},G)\). Thus, \(|\hat{\mu}|-|\mu|=|\hat{\mu}^{(1)}|-|\mu^{(1)}|\leq|\tau|-|\mu^{(1)}|\). From the previous paragraph, the latter is bounded by \(r\). Hence, \(|\hat{\mu}|-|\mu|\leq r\). We now consider the opposite case of Theorem 1. **Theorem 3**. : _Let \((I,G)\) be an HR+SN instance. Suppose that whenever two workers have a firm in common in their preference lists, the two workers do not share an edge in \(G\). Then the matchings of \(I\) are exactly the locally stable matchings of \((I,G)\). Hence, every maximum matching of \(I\) is a maximum locally stable matching of \((I,G)\). Consequently, when \(G\) is the empty graph, the matchings of \(I\) are exactly the locally stable matchings of \((I,G)\), and every maximum matching of \(I\) is a maximum locally stable matching of \((I,G)\)._Proof. : Let \(\mu\) be an arbitrary matching of \(I\). Suppose \(\mu\) is not stable and contains a blocking pair \((f,w)\). In order for \((f,w)\) to be a local blocking pair, \(f\) and \(w\) must have a point of contact \(w^{\prime}\); _i.e._, both \(w\) and \(w^{\prime}\) have \(f\) in their preference lists, and both are neighbors in \(G\). However, by our assumption on \(G\), this cannot be the case. Hence, all blocking pairs of \(\mu\) are not local so \(\mu\) is a locally stable matching of \((I,G)\). Thus, every matching of \(I\) is a locally stable matching of \((I,G)\). Since every locally stable matching of \((I,G)\) is also a matching of \(I\), it follows that the matchings of \(I\) are exactly the locally stable matchings of \((I,G)\). The rest of the theorem follows. In this next theorem, we consider the case when \(G\) is almost an empty graph. **Theorem 4**. : _Suppose that in the HR+SN instance \((I,G)\), \(G\) has a constant number of edges. Then a maximum locally stable matching of \((I,G)\) can be found in time polynomial in \(|I|\)._  
Proof. : Let \(W_{1}\subseteq W\) be the smallest set of workers whose induced subgraph \(G_{1}\) in \(G\) contains all the \(r\) edges of \(G\). Let \(W_{2}=W-W_{1}\), and let \(G_{2}\) be the subgraph induced by \(W_{2}\), which in this case is an empty graph. Thus, \(G=G_{1}\cup G_{2}\). Furthermore, every matching \(\mu\) of \(I\) can be expressed as \(\mu_{1}\cup\mu_{2}\) where each \(\mu_{i}\) is a matching involving the workers in \(W_{i}\), for \(i=1,2\). Let \(I_{1}\) be the HR instance derived from \(I\) by restricting the set of workers to \(W_{1}\). With some abuse in notation, let \(I-\mu_{1}\) be the HR instance obtained from \(I\) by removing the workers matched in \(\mu_{1}\) and decreasing the capacities of the firms according to the number of matches they received in \(\mu_{1}\). Thus, \(\mu_{1}\) is a matching of \(I_{1}\) and \(\mu_{2}\) is a matching of \(I-\mu_{1}\). Conversely, if \(\mu_{1}\) is a matching of \(I_{1}\) and \(\mu_{2}\) is a matching of \(I-\mu_{1}\), putting them together as \(\mu=\mu_{1}\cup\mu_{2}\) results in a matching of \(I\).