Теорема Холла

Нехай ${\displaystyle G=(V,E)\;}$ — деякий граф, і ${\displaystyle A\subseteq V,B\subseteq V\;}$ підмножини його вершин, такі що ${\displaystyle A\cup B=V\;}$, і для довільного ребра ${\displaystyle e\;}$ такого що ${\displaystyle e=\lbrace v,u\rbrace \;}$, справедливе твердження

${\displaystyle (v\in A\land u\in B)\lor (v\in B\land u\in A)\;}$,

тобто граф ${\displaystyle G\;}$ є дводольним. Тоді для даного графу існує набір ребер, що з'єднують вершини ${\displaystyle A\;}$ з різними вершинами ${\displaystyle B\;}$ тоді й лише тоді коли для кожної підмножини елементів ${\displaystyle K\subseteq A\;}$ виконується

${\displaystyle |W|\geqslant |K|,\;}$

де:

${\displaystyle W=\{w\in B\colon (\exists k\in K)\lbrace k,w\rbrace \in E\}\;}$

множина елементів з ${\displaystyle B,\;}$ що з'єднані ребрами хоча б з одним елементом підмножини ${\displaystyle K\;}$ Остання умова також називається умовою одружень.

Нехай S = {S₁, S₂, … } — деяка сім'я скінченних множин. Трансверсалем для S, називається множина X = {x₁, x₂, …} різних елементів (де |X| = |S|) з властивістю, що для всіх i, x_i∈S_i.

Теорема Холла стверджує, що трансверсаль для S існує тоді й лише тоді, коли виконується умова

${\displaystyle |T|\leq {\Bigl |}\bigcup _{t\in T}t{\Bigr |}}$

Доведення здійснюватимемо методом математичної індукції щодо кількості елементів S.

Теорема очевидно справедлива для ${\displaystyle \vert S\vert =0}$. Припустимо твердження теореми справедливе для ${\displaystyle \left\vert S\right\vert <n}$, доведемо її для випадку ${\displaystyle \left\vert S\right\vert =n}$.

Спершу розглянемо випадок коли виконується ${\displaystyle \left\vert \cup T\right\vert \geq \left\vert T\right\vert +1}$ для всіз власних підмножин T of S. Виберемо довільний елемент ${\displaystyle x\in S_{n}}$ представником ${\displaystyle S_{n}.}$ Якщо існує трансверсаль для ${\displaystyle S'=\left\{S_{1}\setminus \{x\},\ldots ,S_{n-1}\setminus \{x\}\right\}}$, тоді ${\displaystyle R'\cup \{x\}}$ є трансверсаллю для S. Але якщо взяти ${\displaystyle \{S_{j_{1}}\setminus \{x\},...,S_{j_{k}}\setminus \{x\}\}=T'\subseteq S'}$ то за припущенням, ${\displaystyle \left\vert \cup T'\right\vert \geq \left\vert \cup _{i=1}^{k}S_{j_{i}}\right\vert -1\geq k}$. Згідно з припущенням індукції для ${\displaystyle S'}$ і як наслідок для ${\displaystyle S}$ існує трансверсаль.

В іншому випадку для деякої ${\displaystyle \emptyset \neq T\subset S}$ виконується рівність ${\displaystyle \left\vert \cup T\right\vert =\left\vert T\right\vert }$. Для ${\displaystyle T}$ маємо, що для кожної ${\displaystyle T'\subseteq T\subset S}$ виконується ${\displaystyle \left\vert \cup T'\right\vert \geq \left\vert T'\right\vert }$, і за припущенням індукції для ${\displaystyle T}$ існує трансверсаль.

Для завершення доведення достатньо знайти представників для множин ${\displaystyle S\setminus T}$ що не містять елементів ${\displaystyle \cup T}$. Для цього достатньо довести, що для довільної множини ${\displaystyle T'\subseteq S\setminus T}$, виконується

${\displaystyle \left\vert \cup T'\setminus \cup T\right\vert \geq \left\vert T'\right\vert }$

і скористатися припущенням індукції.

Маємо

${\displaystyle \left\vert \cup T'\setminus \cup T\right\vert }$

${\displaystyle =\left\vert \bigcup (T\cup T')\right\vert -\left\vert \cup T\right\vert \geq \left\vert T\cup T'\right\vert -\left\vert T\right\vert }$

${\displaystyle =\left\vert T\right\vert +\left\vert T'\right\vert -\left\vert T\right\vert =\left\vert T'\right\vert }$,

зважаючи на відсутність спільних елементів у ${\displaystyle T}$ і ${\displaystyle T'}$, і той факт, що ${\displaystyle \left\vert \cup T\right\vert =\left\vert T\right\vert }$. Тому за припущенням індукції, ${\displaystyle S\setminus T}$ має трансверсаль, що не містить елементів ${\displaystyle \cup T}$.

Позначимо через ${\displaystyle H\;}$ підграф графу ${\displaystyle G=(V,E)\;}$ такий, що

• кожна вершина інцидентна деякому ребру графу ${\displaystyle H\;}$
• граф ${\displaystyle H\;}$ задовольняє умову одружень і є мінімальним за включенням ребер графом, що задовольняє цю вимогу.

Позначимо ${\displaystyle d_{H}(a)\;}$ — степінь вершини a в графі ${\displaystyle H\;}$. Очевидно, що ${\displaystyle d_{H}(a)\geq 1}$. Для доведення теореми Холла достатньо довести, що ${\displaystyle d_{H}(a)=1\;}$.

Для цього спершу позначимо : ${\displaystyle N_{H}(K)=\{w\in B\colon (\exists k\in K)\lbrace k,w\rbrace \in E\}\;}$

Припустимо, що деяка вершини ${\displaystyle a\in A}$ з'єднується більш ніж з однією вершиною і нехай${\displaystyle b_{1},b_{2}\in N_{H}(a).\;}$ Тоді згідно з вибором ${\displaystyle H\;}$ графи ${\displaystyle H-\{ab_{1}\}\;}$ і ${\displaystyle H-\{ab_{2}\}\;}$ не задовольняють умови одружень. Тому для ${\displaystyle i=1,2\;}$ існують такі ${\displaystyle A_{i}\subset A}$ що містять a і ${\displaystyle |A_{i}|>|B_{i}|\;}$ де ${\displaystyle B_{i}:=N_{H-\{ab_{i}\}}(A_{i})\;}$. Звідси одержуємо:

${\displaystyle |N_{H}(A_{1}\cap A_{2}\smallsetminus \{a\})|\leq |B_{1}\cap B_{2}|}$

${\displaystyle =|B_{1}|+|B_{2}|-|B_{1}\cup B_{2}|=|B_{1}|+|B_{2}|-|N_{H}(A_{1}\cup A_{2})}$

${\displaystyle \leq |A_{1}|-1+|A_{2}|-1-|A_{1}\cup A_{2}|=|A_{1}\cap A_{2}\smallsetminus \{a\}|-1}$

Тобто H не задовольняє умови одружень, що суперечить припущенню і доводить теорему.