Теорема Холла (також відома як теорема про одруження)— комбінаторне твердження, що дає достатні і необхідні умови існування вибору різних елементів з деякого набору скінченних множин. Теорема названа на честь англійського математика Філіпа Холла.
Теорема Холла може бути сформульована кількома способами, зокрема за допомогою мови теорії графів і теорії трансверсалів.
Нехай
— деякий граф, і
підмножини його вершин, такі що
, і для довільного ребра
такого що
, справедливе твердження
,
тобто граф
є двочастковим. Тоді для даного графа існує набір ребер, що з'єднують вершини
з різними вершинами
тоді й лише тоді коли для кожної підмножини елементів
виконується
![{\displaystyle |W|\geqslant |K|,\;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0c17108d3a136a4a49d905ce89b4e8f78566b45d)
де:
![{\displaystyle W=\{w\in B\colon (\exists k\in K)\lbrace k,w\rbrace \in E\}\;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7e7eae476cba9ee1faa0a251e599b8561834e2b4)
множина елементів з
що з'єднані ребрами хоча б з одним елементом підмножини
Остання умова також називається умовою одружень.
Нехай S = {S1, S2, … } — деяка сім'я скінченних множин. Трансверсалем для S, називається множина X = {x1, x2, …} різних елементів (де |X| = |S|) з властивістю, що для всіх i, xi∈Si.
Теорема Холла стверджує, що трансверсаль для S існує тоді й лише тоді, коли виконується умова
![{\displaystyle |T|\leq {\Bigl |}\bigcup _{t\in T}t{\Bigr |}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0802b47a9143761423322d8b6154c96da768b4d6)
Доведення здійснюватимемо методом математичної індукції щодо кількості елементів S.
Теорема очевидно справедлива для
.
Припустимо твердження теореми справедливе для
, доведемо її для випадку
.
Спершу розглянемо випадок коли виконується
для всіз власних підмножин T of S. Виберемо довільний елемент
представником
Якщо існує трансверсаль для
, тоді
є трансверсаллю для S.
Але якщо взяти
то за припущенням,
.
Згідно з припущенням індукції для
і як наслідок для
існує трансверсаль.
В іншому випадку для деякої
виконується рівність
.
Для
маємо, що для кожної
виконується
,
і за припущенням індукції для
існує трансверсаль.
Для завершення доведення достатньо знайти представників для множин
що не містять елементів
. Для цього достатньо довести, що для довільної множини
, виконується
![{\displaystyle \left\vert \cup T'\setminus \cup T\right\vert \geq \left\vert T'\right\vert }](https://wikimedia.org/api/rest_v1/media/math/render/svg/8a6cb76b7af9a02ee1685fc219274794de5eee1c)
і скористатися припущенням індукції.
Маємо
,
зважаючи на відсутність спільних елементів у
і
, і той факт, що
. Тому за припущенням індукції,
має трансверсаль, що не містить елементів
.
Позначимо через
підграф графа
такий, що
- кожна вершина інцидентна деякому ребру графа
![{\displaystyle H\;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a3a6b41f082883b2f8b38e8a09742fda0e5e25a0)
- граф
задовольняє умову одружень і є мінімальним за включенням ребер графом, що задовольняє цю вимогу.
Позначимо
— степінь вершини a в графі
. Очевидно, що
. Для доведення теореми Холла достатньо довести, що
.
Для цього спершу позначимо :
Припустимо, що деяка вершини
з'єднується більш ніж з однією вершиною і нехай
Тоді згідно з вибором
графи
і
не задовольняють умови одружень. Тому для
існують такі
що містять a і
де
.
Звідси одержуємо:
![{\displaystyle |N_{H}(A_{1}\cap A_{2}\smallsetminus \{a\})|\leq |B_{1}\cap B_{2}|}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4fab3b5901efde428448d15b8aeb86e791ef851b)
![{\displaystyle =|B_{1}|+|B_{2}|-|B_{1}\cup B_{2}|=|B_{1}|+|B_{2}|-|N_{H}(A_{1}\cup A_{2})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/873b6002bf79c1d1876732cbf4a6ec23cf3d07f9)
![{\displaystyle \leq |A_{1}|-1+|A_{2}|-1-|A_{1}\cup A_{2}|=|A_{1}\cap A_{2}\smallsetminus \{a\}|-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/de8ce7a15270ff1ba23a92f4e33405f17206572e)
Тобто H не задовольняє умови одружень, що суперечить припущенню і доводить теорему.