Теорема про два вуха

Вухо багатокутника визначається як вершина v така, що відрізок лінії між двома вершинами, які суміжні (з'єднані ребром) v, повністю лежить у внутрішній частині багатокутника. Теорема про два вуха стверджує, що кожен простий багатокутник має щонайменше два вуха.

Вухо та дві його суміжні вершини утворюють трикутник у межах багатокутника, який не перетинається жодною іншою частиною багатокутника. Якщо вилучити трикутник такого типу, утворюється багатокутник з меншою кількістю сторін, а багаторазове видалення вух дозволяє тріангулювати будь-який простий багатокутник.

І навпаки, якщо багатокутник трикутний, слабко двоїстий граф тріангуляції (граф в якому одна вершина відповідає одному трикутнику, а одне ребро — парі суміжних трикутників) буде деревом і кожен лист дерева відповідатиме вуху. Оскільки кожне дерево більш ніж з однією вершиною має щонайменше два листки, кожен тріангульований багатокутник, в якому більш ніж один трикутник, має принаймні два вуха. Таким чином, теорема про два вуха рівносильна тому, що кожен простий багатокутник має тріангуляцію[1].

Вухо називають оголеним, коли воно утворює вершину опуклої оболонки багатокутника. Однак багатокутник може й не мати оголених вух[2].

Вуха є окремим випадком головної вершини, а саме такою, що відрізок лінії, який з'єднує суміжні вершини, не перетинає багатокутник і не торкається будь-якої іншої його вершини. Основна вершина, для якої цей відрізок не належить багатокутнику, називається ротом. Аналогічно теоремі про два вуха, кожен не опуклий простий багатокутник має щонайменше один рота. Багатокутники з мінімальною кількістю головних вершин обох типів, а саме, рівно з двома вухами та одним ротом, називаються антропоморфними багатокутниками[3].

Теорему про два вуха часто пов'язують зі статтею Гарі Х. Мейстерса 1975 року, з якого і походить термінологія «вуха»[4]. Однак теорема була доведена раніше Максом Деном (близько 1899 року) як частина доказу теореми Жордана. Для доведення теореми, Ден зауважує, що кожен багатокутник має щонайменше три опуклі вершини. Якщо одна з цих вершин, v, не є вухом, то вона може бути з'єднана по діагоналі з іншою вершиною x всередині трикутника uvw утвореної v і двома його суміжними; x може бути вершиною у цьому трикутнику, та буде найвіддаленішою від лінії uw. Ця діагональ ділить багатокутник на два менші багатокутники, і повторний поділ на вуха та діагоналі призводить до тріангуляції всього многокутника, з якого вухо може бути знайдено як лист двоїстого дерева[5].

• Meisters' Two Ears Theorem, Cut-the-Knot (англ.)
• The Two-Ears Theorem, Готфрід Тусайн (англ.)
• Weisstein, Eric W. Two-Ears Theorem(англ.) на сайті Wolfram MathWorld.