Изменения

\bigg(\cfrac{e^{(\tfrac{1 - \epsilon)/}{\epsilon}} \cdot

Положим <tex>m = Const * kd</tex> (с достаточно большим значением <tex>Const</tex>), чтобы для всех возможных s выполнялось неравенство <tex>\cfrac{e^{(\tfrac{1 - \epsilon)/}{\epsilon}} \cdot (1 - \epsilon)sd}{m} \leqslant \cfrac{1}{2}</tex>. Тогда выражение в квадратных скобках не превосходит <tex>\cfrac{ne}{2 ^ {\epsilon d}}</tex>. Остаётся выбрать <tex>d > \cfrac{1}{\epsilon}\log(2en)</tex>, и мы получаем <tex>\cfrac{ne}{2^{\epsilon d}} < \cfrac{1}{2}</tex>.

 1. # <tex>\forall S: S \supseteq L, |S| \neq 0</tex> строго расширяется, то есть <tex>|\Gamma(S)| > |S|</tex>. Выберем <tex>\forall x: x \supset V(L) : (x, y) \in E</tex>. Тогда рассмотрим двудольный граф <tex>G^{*}</tex>, у которого левая доля <tex>L^{*} = L \diagdown {x}</tex>, а правая <tex>R^{*} = R \diagdown {y}</tex>. Так как <tex>\forall S: S \supset L</tex> удовлетворяет строгому неравенству теоремы, то каждое подмножество <tex>L^{*}</tex> удовлетворяет неравенству, поскольку только одна вершина <tex>y</tex> была удалена из <tex>R</tex>. Следовательно, по предположению индукции меньший граф <tex>G^{*}</tex> имеет паросочетание. К этому паросочетанию добавляем ребро (x, y) что дает совершенное паросочетание. 2. # Пусть <tex>\exists\ T \in L, \ |T| \neq 0</tex> такое, что <tex>|\Gamma(T)| = |T|</tex>. Рассмотрим порожденные графы <tex>G_{1} = T \cup \Gamma(T)</tex> и <tex>G_{2} = L \diagdown T \cup R \diagdown \Gamma(T)</tex>. По предположению индукции <tex>G_{1}</tex> имеет совершенное паросочетание (Заметим, что предположение индукции не может использовано непосредственно на <tex>G_{2}</tex>). Пусть <tex>S \supseteq L \diagdown T</tex>, тогда: <tex> \Gamma_{G_{2}}(S) = \Gamma_{G}(S \cup T) \diagdown \Gamma_{G}(T) \ \Rightarrow</tex> <tex>|\Gamma_{G_{2}}| \geqslant |S \cup T| - |T| = |S|</tex> Неравенство верно, поскольку <tex>S \cup T</tex> удовлетворяет <tex>|\Gamma_{G}(S \cup T)| \geqslant |S \cup T|</tex> и по предположению <tex>|\Gamma_{G}(T)| = |T|</tex>. Следовательно, <tex>G_{2}</tex> также удовлетворяет неравенству теоремы и по предположению индукции имеет паросочетание. Объединение совершенных паросочетаний <tex>G_{1}</tex> и <tex>G_{2}</tex> {{---}} паросочетание для <tex>G</tex>.

[[Алгебра|Алгебраическое]] конструирование, основанное на графах Кэли<ref>[[wikipedia:Cayley_graph|Wikipedia {{---}} граф Кэли]]</ref>, известно для различных вариантов экспандеров. Следующее конструирование принадлежит Маргулису и было проанализировано Габбером и Галилом <ref>Omer Reingold Undirected connectivity in log-space // Journal of the ACM. — 2008. — Т. 55, вып. 4. — DOI:10.1145/1391289.1391291</ref>. Для любого натурального <tex>n</tex> строим граф, <tex>G_{n}</tex> со множеством  В качестве множества вершин графа возьмём <tex>V = \mathbb Z _{n}\times \mathbb {Z} _{n}</tex>(таким образом, где граф будет содержать <tex>\mathbb n^{Z2} _{n}=\mathbb Z /n \mathbb Z</tex> вершин). Для любой вершины Каждая вершина <tex>(x,y)\in </tex> из <tex>\mathbb {Z} _{n}\times \mathbb {Z} _{n}</tex>, её восемь соседей будутсоединяется рёбрами со следующими восьмую вершинами: