21 доказательство формулы Эйлера

Для связного вложенного планарного графа \(G\) определим двойственный граф \(G^*\): в каждой грани \(G\) поместим вершину и соединим вершины двух соседних граней кривой \(e^*\), проходящей через их общее ребро \(e\). Заметим, что \(G^{**}=G\). По теореме Жордана любой цикл в \(G\) разъединяет \(G^*\). Любой ациклический подграф \(F\) графа \(G\) есть лес и не разъединяет \(G^*\) (из любой грани можно попасть в любую другую, обходя деревья леса \(F\)). Таким образом, связность и ацикличность двойственны друг другу. Эта двойственность лежит в основе следующего доказательства.

Выберем в \(G\) произвольное остовное дерево \(T\) — связный ациклический подграф. Двойственные рёбра его дополнения, \((G\setminus T)^*\), образуют ациклический связный подграф графа \(G^*\), то есть тоже остовное дерево. Вместе оба дерева содержат \((V-1)+(F-1)\) рёбер.

Это доказательство — моё любимое; именно его я использую при чтении курса теории графов. Зоммервиль приписывает его фон Штаудту. Оно хорошо сочетается с другими проявлениями планарной двойственности, например, с тем, что всякий планарный граф с чётными гранями двудолен (по двойственности из эйлеровых обходов). У ряда других доказательств формулы Эйлера есть две версии — в графе и в двойственном графе, — но это доказательство самодвойственно, как и сама формула.

Идея разложения графа в чередующиеся деревья нашла применение в ряде алгоритмов, включая работы автора и других исследователей по динамическим минимальным остовным деревьям, а также работы Гудрича и Тамассии по задаче о расположении точки. У этой идеи есть и связи с разводкой питания в VLSI и с анализом водосборов.

Формулу можно доказать для всех связных планарных графов индукцией по числу граней графа \(G\).

Если \(G\) имеет единственную грань, то по теореме Жордана он ацикличен и связен, то есть является деревом, и \(E=V-1\). Иначе выберем ребро \(e\), разделяющее две различные грани \(G\), и удалим его; \(e\) входит в границу каждой из двух граней не более одного раза, поэтому граф остаётся связным — любой путь через \(e\) можно заменить путём вдоль другой стороны одной из двух граней. При удалении число граней и рёбер уменьшается на единицу, и результат следует по индукции.

Это доказательство часто встречается в учебниках по теории графов (например, у Бонди и Мёрти), но мне оно нравится менее всего: оно неоправданно громоздко и неизящно; полное обоснование некоторых шагов требует не меньших усилий, чем всё первое доказательство. Оно плохо обобщается, и авторы учебников нередко опускают критически важные детали.

Этот аргумент планарно двойствен доказательству индукцией по граням.

Если \(G\) имеет единственную вершину, каждое ребро есть жорданова кривая, поэтому граней \(E+1\), и \(F+V-E=(E+1)+1-E=2\). Иначе выберем ребро \(e\), соединяющее две различные вершины \(G\), и стянем его. При этом число вершин и рёбер уменьшается на единицу, и результат следует по индукции.

Объединив два предыдущих доказательства — индукцию по граням и индукцию по вершинам, — получаем ещё одно индукционное доказательство с более простым базовым случаем.

Если связный планарный мультиграф \(G\) не имеет рёбер, он состоит из изолированной вершины, и \(V+F-E=1+1-0=2\). Иначе выберем произвольное ребро \(e\). Если \(e\) соединяет две различные вершины, стянем его, уменьшив \(V\) и \(E\) на единицу. Иначе \(e\) — петля, соединяющая вершину с собой. Она образует жорданову кривую и разделяет две грани; удалим её, уменьшив \(F\) и \(E\) на единицу. В обоих случаях результат следует по индукции.

Это доказательство использовано у ван Линта и Вильсона. Возможны и другие варианты: если \(e\) одновременно соединяет две вершины и разделяет две грани, можно по-разному выбирать, удалять или стягивать \(e\).

Это доказательство было прислано мне Алексом Богомольным, который нашёл его в русском переводе (1958) 7-го издания «Элементарной геометрии» Ж. Адамара (т. 2). Оно тесно связано с доказательством через разложение по ушам.

Доказательство проводится индукцией по числу граней. Сначала удалим одну грань и докажем формулу \(V-E+F=1\) для открытых многогранных поверхностей. Для единственной грани формула очевидна. Предположим, что формула верна при числе граней, меньшем \(F\), и рассмотрим поверхность с \(F\) гранями. Выберем две вершины на границе (оставшейся после удаления грани) и соединим их цепью внутренних рёбер. (Существование такой цепи следует из варианта теоремы Жордана.) Разрежем вдоль этой цепи. Получатся две поверхности, для каждой из которых формула \(V-E+F=1\) выполнена. Пусть для первой это \(V_1-E_1+F_1=1\), для второй — \(V_2-E_2+F_2=1\). Предположим, что цепь содержит \(L\) рёбер и, значит, \(L+1\) вершину. Тогда \(E_1+E_2=E+L\) и \(V_1+V_2=V+L+1\). Разумеется, \(F_1+F_2=F\). Сложение даёт нужный результат.

Можно использовать и двойственную версию доказательства, в которой открытый диск (полученный удалением вершины из многогранника) разбивается чередующимися последовательностями рёбер и граней.

Это доказательство принадлежит Тёрстону.

Расположим многогранник в пространстве так, чтобы ни одно ребро не было горизонтальным — в частности, чтобы существовала ровно одна верхняя вершина \(U\) и одна нижняя вершина \(L\).

Поместим единичный положительный заряд в каждую вершину, единичный отрицательный заряд в центр каждого ребра и единичный положительный заряд в середину каждой грани. Покажем, что все заряды сокращаются, кроме зарядов в \(L\) и \(U\). Для этого сдвинем все заряды вершин и рёбер в соседнюю грань, а направление сдвига определим правилом: каждый заряд движется горизонтально, против часовой стрелки при виде сверху.

При этом каждая грань получает суммарный заряд от открытого интервала вдоль своей границы. Этот интервал разбивается на чередующиеся рёбра и вершины. Поскольку первым и последним элементом являются рёбра, отрицательных зарядов на один больше; поэтому суммарный заряд в каждой грани равен нулю. Остаётся \(+2\) — заряды \(L\) и \(U\).

Тёрстон обобщает эту идею до доказательства того, что эйлерова характеристика является инвариантом любого триангулированного гладкого многообразия.

Вместо группировки зарядов по граням можно привести двойственный аргумент, группируя заряды по вершинам. Это доказательство лучше всего работает с выпуклым планарным вложением графа многогранника — его диаграммой Шлегеля. Доказательство через проекцию Шлегеля близко по духу, но перераспределяет заряды иначе.

Повернём граф так, чтобы ни одно ребро не было вертикальным. Как и в предыдущем доказательстве, поместим единичный положительный заряд в каждую вершину, единичный отрицательный заряд в центр каждого ребра и единичный положительный заряд в середину каждой грани. Покажем, что все заряды, кроме двух положительных, сокращаются. Для этого сдвинем заряд каждого ребра в его правый конец; заряд каждой грани (кроме внешней) сдвинем в её самую правую вершину. Каждая вершина (кроме самой левой) получает заряды от чередующейся последовательности рёбер и граней, которые компенсируют её начальный заряд. Единственные некомпенсированные заряды — положительный заряд на внешней грани и положительный заряд на самой левой вершине.

Это доказательство использует тот факт, что планарный граф многогранника можно вложить так, что все рёбра — отрезки прямых.

Просуммируем углы в каждой грани прямолинейного вложения графа (включая внешнюю грань); сумма углов \(k\)-угольника равна \((k-2)\pi\), и каждое ребро принадлежит двум граням, поэтому полная сумма равна \((2E-2F)\pi\).

Подсчитаем те же углы иначе. Каждая внутренняя вершина окружена гранями и вносит в сумму \(2\pi\). Вершины на внешней грани вносят \(2(\pi - \theta_v)\), где \(\theta_v\) — внешний угол многоугольника при вершине \(v\). Полный внешний угол любого многоугольника равен \(2\pi\), поэтому полная сумма равна \(2\pi V - 4\pi\).

Приравнивая две формулы и деля на \(2\pi\), получаем \(V - 2 = E - F\), то есть \(V-E+F=2\).

Таким методом пользовался Декарт в 1630 году. Зоммервиль приписывает это доказательство Люилье и Штейнеру. Хилтон и Педерсон аналогичным образом используют углы для связи эйлеровой характеристики многогранной поверхности с её полным угловым дефектом.

Доказательство через сумму углов работает чище в терминах сферических триангуляций, главным образом потому, что при таком подходе нет выделенной «внешней грани».

Нам потребуется следующий факт сферической тригонометрии: на единичной сфере площади \(4\pi\) для любого треугольника, образованного дугами больших кругов, сумма трёх внутренних углов равна \(\pi+a\), где \(a\) — избыток треугольника — совпадает с его площадью. См., напр., Уэллс, с. 238.

Чтобы перевести задачу о многогранниках на язык сферической геометрии, сначала триангулируем многогранник; каждое новое ребро увеличивает \(E\) и \(F\) на единицу, не меняя \(V-E+F\). Теперь проведём опыт, аналогичный описанному на главной странице: поместим источник света во внутреннюю точку многогранника, а сферический экран — вокруг него, с центром в точке источника. Тени рёбер многогранника на экране образуют сферическую триангуляцию. Поскольку каждое ребро принадлежит двум треугольникам, а у каждого треугольника три ребра, \(2E=3F\).

Просуммируем углы всех треугольников. По приведённому выше факту сферической тригонометрии сумма равна \((4+F)\pi\). Та же сумма, вычисленная через вершины, даёт \(2V\pi\). Приравнивая, получаем \(F=2V-4\), а в сочетании с \(2E=3F\) — искомый результат.

Зоммервиль приписывает это доказательство Лежандру. Благодаря связям с геометрической топологией именно это доказательство используется у Уикса, который также приводит изящное доказательство соотношения между углом и площадью на основе включения-исключения для двугранных клиньев.

Соотношение \(Ak = 2\pi (V-E+F)\) на поверхности постоянной кривизны \(k\) (такой как сфера) представляет собой форму теоремы Гаусса–Бонне из дифференциальной геометрии.

Мы перевели наше доказательство через сумму углов на язык сферической тригонометрии, попутно получив формулы в терминах сумм площадей граней. Теперь рассмотрим аналогичные формулы для сумм площадей в планарной геометрии, следуя идее Уэллса.

Основной инструмент — формула Пика: для любого многоугольника \(P\), вершины которого имеют целочисленные координаты, площадь равна \(N + B/2 - 1\), где \(N\) — число целых внутренних точек, а \(B\) — число целых точек на сторонах и вершинах \(P\). Формула Пика доказывается без формулы Эйлера (например, через знаковые площади трапеций), так что порочного круга нет.

Нарисуем планарный граф с прямолинейными рёбрами. Можно выбрать достаточно малый радиус \(r\) такой, что сдвиг каждой вершины в пределах круга радиуса \(r\) сохраняет планарность; масштабируем граф так, чтобы \(r=1\). Сдвинем каждую вершину в ближайшую целую точку; результат — эквивалентный планарный граф на целочисленной решётке.

Внешняя грань покрывается остальными гранями ровно один раз, поэтому сумма площадей внутренних граней равна площади внешней грани. По формуле Пика эта сумма площадей равна \(I+X+B/2+S/2-(F-1)\), где \(I\) — число точек, внутренних для одной из граней, \(X\) — число точек на внутренних рёбрах (каждая учитывается как \(1/2\) в каждой из двух граней), \(S\) — сумма (по всем вершинам) числа внутренних граней, которым принадлежит вершина, а \((F-1)\) — вклад слагаемого \(-1\) из каждого из \(F-1\) применений формулы Пика.

Внутренняя вершина вносит в \(S\) вклад, равный её степени, а вершина на внешней грани — степень минус один. Поэтому \(S=2E-K\), где \(K\) — число вершин на внешней грани. По формуле Пика площадь внешней грани равна \((I+X+V-K)+(B+K)/2-1\). Из уравнений \(S=2E-K\) и \(I+X+B/2+S/2-(F-1)=(I+X+V-K)+(B+K)/2-1\) следует результат.

К сожалению, формула Пика не обобщается на старшие размерности, поэтому такой подход вряд ли пригоден для доказательства многомерных аналогов формулы Эйлера.

Граф называется рёберно двусвязным, если удаление любого ребра сохраняет связность. Рёберная двусвязность эквивалентна существованию разложения по ушам: разбиения множества рёбер графа в последовательность ушей (простых путей и циклов), причём первое ухо — одна вершина; начало и конец каждого следующего уха — вершины предыдущих ушей, а все остальные вершины уха — новые. Такое разложение строится последовательно: каждое ухо начинается неиспользованным ребром \(e\) из уже исследованной вершины и продолжается кратчайшим путём обратно к другой исследованной вершине (такой путь существует, поскольку \(e\) не может разъединить граф).

Применим такое разложение к доказательству формулы Эйлера для многогранников.

Граф \(G\) многогранника рёберно двусвязен: при удалении ребра \(e\) его концы по-прежнему соединимы путём вдоль другой стороны одной из двух граней \(G\), содержащих \(e\).

Найдём разложение \(G\) по ушам и рассмотрим процесс построения \(G\) последовательным добавлением ушей, начиная с одной вершины. Вначале имеется одна вершина, одна грань и ни одного ребра. Каждое новое ухо образует путь, соединяющий две вершины на границе некоторой грани, и разбивает эту грань надвое; в пути на одно ребро больше, чем вершин. Если ухо имеет \(k\) рёбер, его добавление увеличивает \(V\) на \(k-1\), \(E\) на \(k\) и \(F\) на \(1\), и результат следует по индукции по числу ушей.

Разложения по ушам особенно полезны при разработке параллельных алгоритмов, поскольку их легче находить параллельно, чем, скажем, деревья поиска в глубину. См., напр., работу автора по распознаванию последовательно-параллельных графов.

Циглер рассматривает многогранник (многогранный комплекс) как набор граней различных размерностей. Он обозначает \(f_i\) число граней размерности \(i\): \(f_0=V\), \(f_1=E\), \(f_2=F\), а также добавляет грани размерности \(d\) (весь многогранник) и \(-1\) (пустая грань); \(f_{-1}=f_d=1\). Эти две дополнительные грани — верхний и нижний элементы решётки граней многогранника.

Циглер определяет послойное построение комплекса многогранных граней как линейный порядок на гранях максимальной размерности (гипергранях), удовлетворяющий (при размерности гиперграней не менее единицы) следующим условиям:

1. Граница первой гиперграни \(F_0\) допускает послойное построение.
2. Пересечение каждой гиперграни \(F_j\) (\(j>0\)) с объединением предыдущих гиперграней непусто и образует начальный отрезок послойного построения гиперграни \(F_j\).

У всякого выпуклого многогранника есть послойное построение, получаемое так: проведём прямую из точки вблизи одной грани и упорядочим гиперграни по порядку, в котором при движении вдоль прямой плоскость гиперграни пересекается и гипергрань становится видимой. (Прямая должна проходить «на бесконечность и обратно» через другую сторону многогранника.) Пересечение гиперграни \(F_j\) с предыдущими гипергранями геометрически определяется как часть границы \(F_j\), видимая из точки пересечения смотровой прямой с плоскостью \(F_j\); это показывает, что требуемое послойное построение младшей размерности устроено аналогично.

Затем Циглер доказывает, что эйлерова характеристика любого многогранника \[\chi(P)=\sum_{i=-1}^d (-1)^i f_i = 0\] индукцией по размерности и длине построения:

Базовый случай, когда \(f_{-1}=f_0=1\), тривиален. Пусть \(P\) — \(d\)-мерный многогранник с порядком послойного построения \(F_1,F_2,\dots\). Тогда \[\chi(F_1\cup F_2\cup\cdots\cup F_j)\] равна \(0\) при \(j < f_{d-1}\) и \(1\) при \(j=f_{d-1}\). Это следует индукцией по \(j\): добавляемые гиперграни суть \((d-1)\)-мерные многогранники, эйлерова характеристика аддитивна, а пересечение \(F_j\) с предыдущими гипергранями — часть границы \(F_j\), допускающая послойное построение, но (при \(j < f_{d-1}\)) не вся граница. (Циглер доказывает это в общем случае; для описанного выше геометрического построения это наглядно.)

Удаление двух «дополнительных» граней \(f_{-1}\) и \(f_3\) из суммы даёт обычную формулу Эйлера.

Это доказательство — вариация послойного построения, включённая здесь ввиду исторической значимости: его использовал Коши, а подробно исследовал Лакатош.

Начнём с выпуклого планарного вложения рёбер многогранника. Если есть нетреугольная грань, добавим диагональ, разбив грань на две и увеличив число рёбер и граней на единицу; результат следует по индукции.

Пусть теперь все внутренние грани — треугольники, их не менее двух, и из любой внутренней точки можно попасть в любую другую путём, не пересекающим границу внешней грани. (Триангуляция выпуклого вложения многогранника удовлетворяет этим условиям.) Тогда всегда найдутся хотя бы два треугольника с ребром на границе, удаление любого из которых даёт один треугольник или меньший граф того же типа; это доказывается индукцией по числу треугольников: если некий граничный треугольник разъединяет внутренние точки, то две компоненты на его двух неграничных рёбрах — либо одиночные треугольники (удалимые), либо (по индукции) графы с двумя удалимыми граничными треугольниками, хотя бы один из которых удалим и в исходном графе.

Удаляем граничные треугольники по одному; на каждом шаге удаляется либо одно ребро и одна грань, либо два ребра, одна грань и одна вершина. В обоих случаях \(V-E+F\) не меняется. В итоге остаётся единственный треугольник, для которого \(V-E+F=3-3+2=2\).

Разбор случаев в многомерных версиях этого доказательства тесно связан с теоремой Радона (любые \(d+2\) точки можно разбить на два подмножества с пересекающимися выпуклыми оболочками) и с алгоритмами построения триангуляций Делоне и выпуклых оболочек на основе «перестроек».

Элементы этого доказательства описаны у Бишопа и Голдберга.

Определим функцию высоты на поверхности многогранника. Выберем произвольные высоты для вершин. На каждом ребре выберем внутреннюю точку с высотой, большей высот обоих концов, и линейно интерполируем на оставшихся участках ребра. На каждой грани выберем внутреннюю точку с высотой, большей всех высот на границе, и линейно интерполируем вдоль отрезков от этой точки до границы. Получается непрерывная функция с \(V+F+E\) критическими точками: \(V\) локальных минимумов в вершинах, \(E\) сёдел в выбранных точках рёбер и \(F\) локальных максимумов в выбранных точках граней.

Представим поверхность как изначально сухую землю, на которую обрушивается потоп, постепенно покрывающий высочайшую вершину. Подсчитаем число озёр и связных участков суши, возникающих и исчезающих в этом потопе.

Каждому локальному минимуму соответствует образование одного озера. При каждом седле либо два озера сливаются, либо одно озеро замыкается само на себя, отрезая участок суши (обозначим число таких событий \(J\) и \(D\) соответственно). При каждом пике исчезает один участок суши. В начале имеется один участок суши, в конце — одно глобальное озеро. Поэтому \(1+D-F=0\) и \(0+V-J=1\). Из этих двух уравнений и равенства \(D+J=E\) следует результат.

Можно считать, что дождь (неестественным образом) поддерживает одинаковый уровень воды повсюду, так что два озера достигают седла одновременно; или можно принять более реалистичную точку зрения, при которой осадки варьируются, но когда одно озеро достигает седла, вода переливается, пока уровень озера по другую сторону не сравняется.

Это доказательство почти самодвойственно; главная асимметрия — в определении функции высоты. Как обычно, используется теорема Жордана: озеро, замкнувшееся само на себя, создаёт остров. Классификация особых точек (пики, сёдла, впадины) для функции высоты на поверхности — основная идея теории Морса, но это доказательство восходит к публикации Мёбиуса 1863 года, задолго до Морса.

Элементы следующего доказательства описаны у Лакатоша (который приписывает его Пуанкаре), однако Лакатош опускает детальное обоснование свойств отображения \(\partial\), определённого ниже, принимая их за аксиомы. (Фактически доказываемая им теорема — формула Эйлера для любого многогранника, удовлетворяющего этим аксиомам, но без доказательства того, что выпуклые многогранники им удовлетворяют.)

Как и в доказательстве через послойное построение, рассматриваем многогранник как комплекс граней различных размерностей, с \(f_i\) гранями размерности \(i\). Добавляем две «дополнительные» грани: весь многогранник и пустую грань, \(f_{-1}=f_d=1\).

Подмножества граней размерности \(i\) рассматриваются как векторное пространство над полем \(\mathbb{Z}_2\) из двух элементов, где сложение — симметрическая разность подмножеств (XOR). Так получается \(d+1\) векторных пространств \(V_i\) размерности \(f_i\). Множества граней многогранника образуют базисы этих пространств.

Эти пространства снабжены линейным отображением \(\partial\), переводящим \(V_i\) в \(V_{i-1}\): образ грани — множество её гиперграней. Если \(v\) — сумма граней, то \(\partial v\) — сумма соответствующих множеств гиперграней. (У пустой грани нет гиперграней; гипергранью вершины считается пустая грань.) Отображение \(\partial\) обладает двумя важными свойствами:

1. У границ нет границ. Для любого вектора \(v\) выполнено \(\partial\partial v=0\). Если \(v\) — базисный вектор (одна грань), это верно потому, что каждая грань размерности на два ниже, чем \(v\), разделяет две гиперграни \(v\) и потому сокращается в \(\partial\partial v\). Для пустой грани \(\partial v=0\), и для любого линейного отображения \(\partial 0=0\). Для вершины \(\partial v\) — пустая грань, и снова \(\partial\partial v=0\). Для остальных векторов результат следует по линейности.

2. Вектор без границы сам является границей. Если \(\partial v=0\), то \(v=\partial w\) для некоторого \(w\). Для \(v=0\) можно взять \(w=0\). Для ненулевого \(v\) разберём по размерностям. Если \(v \in V_{-1}\), то это пустая грань, являющаяся границей некоторой вершины. Если \(v \in V_0\), для \(\partial v=0\) вершин должно быть чётное число; объединим их в пары и соединим путями; \(w\) — сумма этих путей. Если \(v \in V_1\), рёбра из \(v\) встречают каждую вершину чётное число раз; они группируются в жордановы кривые, и \(w\) — сумма ограниченных ими областей. Если \(v \in V_2\), это должно быть всё множество гиперграней многогранника: из любой гиперграни можно попасть в любую другую путём по границе (минуя вершины), и ни одно пересечённое ребро не лежит в \(\partial v\). Тогда \(w\) — ячейка, соответствующая всему многограннику. Если \(v\) — ненулевой вектор из \(V_3\), то \(\partial v\) не может быть нулём.

Теперь можно приступить к доказательству \(\sum_{i=-1}^d (-1)^i f_i=0\).

Пусть \(B_i\) — подпространство \(V_i\), состоящее из векторов \(v\) с \(\partial v=0\). Отображение \(\partial\) переводит \(V_i\) в \(B_{i-1}\). Для любого линейного отображения исходное пространство разлагается в ядро (множество векторов, переходящих в нуль, — здесь \(B_i\)) и его ортогональное дополнение, изоморфное образу. Поэтому \(\dim V_i=\dim B_i+\dim B_{i-1}\). Подставляя в нужную сумму: \[ \sum_{i=-1}^d (-1)^i f_i = \sum_{i=-1}^d (-1)^i (\dim B_i+\dim B_{i-1}), \] что равно нулю, так как каждое слагаемое \(B_i\) входит дважды с противоположными знаками.

Удаление двух добавленных параметров \(f_{-1}\) и \(f_3\) даёт обычную формулу Эйлера. Вероятно, существует более прямой, «безразмерный» способ доказать, что бесграничные векторы сами являются границами, но я его не вижу, и Лакатош его не описывает.

Теория гомологий — один из краеугольных камней алгебраической топологии — посвящена определению аналогичных пространств и изучению того, в какой мере ключевое равенство \(\dim V_i=\dim B_i+\dim B_{i-1}\) нарушается для других топологических пространств.

Двоичное разбиение пространства (BSP) — структура данных, широко используемая в компьютерной графике и геометрическом поиске. Она строится разрезанием пространства гиперплоскостью с рекурсивным разбиением каждого полупространства. Результат — иерархическое разбиение на выпуклые ячейки.

В 1974 году Хельге Тверберг показал, что для любого выпуклого многогранника \(K\) существует двоичное разбиение, разлагающее \(K\) на симплексы. Для двумерных многоугольников это тривиально (достаточно последовательно проводить диагонали); общий случай доказывается индукцией по размерности и числу гиперграней:

Предполагаем, что \(K\) не симплекс (иначе всё доказано).

Если \(K\) имеет вершину \(P\), инцидентную более чем \(d\) гиперграням, то (по индукции по размерности) можно разрезать \(K\) гиперплоскостями через \(P\) на меньшие многогранники, каждый из которых имеет ровно \(d\) гиперграней, инцидентных \(P\). Число гиперграней, не инцидентных \(P\), в каждом таком многограннике не превышает числа гиперграней \(K\), поэтому гиперграней стало меньше. По индукции каждый из них разбивается на симплексы.

Пусть теперь каждая вершина \(K\) инцидентна ровно \(d\) гиперграням. Выберем вершину \(P\), не смежную с двумя гипергранями \(F_1\) и \(F_2\). (Такие \(P\), \(F_1\), \(F_2\) находятся по индукции по размерности, если у \(K\) есть гипергрань, не являющаяся симплексом; если же все гиперграни — симплексы, берём две смежные гиперграни \(F_1\), \(F_2\) и любую вершину \(P\), отличную от \(d+1\) вершин, общих у \(F_1\) и \(F_2\).) Пусть \(L\) — пересечение гиперплоскостей, содержащих \(F_1\) и \(F_2\); разрежем \(K\) гиперплоскостью через \(P\) и \(L\). Каждая из двух частей не содержит одну из гиперграней \(F_i\), но приобретает новую гипергрань на плоскости разреза, так что число гиперграней не растёт. Можно показать, что каждая часть либо имеет более \(d\) гиперграней при \(P\) (и можно применить предыдущий случай), либо не содержит дополнительную гипергрань \(K\) (и можно применить индукцию по числу гиперграней); в обоих случаях разбиение продолжается рекурсивно.

Число разрезов может быть экспоненциальным по числу гиперграней, но этого, по-видимому, не избежать из-за примеров типа гиперкуба.

Затем Тверберг доказывает, что эйлерова характеристика \(\chi(K)\) (определённая как для послойного построения) всегда равна нулю, индукцией по размерности и числу разрезов:

Если \(K\) — симплекс, числа граней каждой размерности выражаются через биномиальные коэффициенты, и тождество \(\chi(K)=0\) — это применение бинома Ньютона к вычислению \((1+x)^d\) при \(x=-1\).

Иначе пусть верхний разрез разбивает \(K\) на два многогранника \(K_1\) и \(K_2\). Пусть \(K_3\) — выпуклая оболочка множества вершин \(K\), лежащих в секущей гиперплоскости, а \(K_4\) — пересечение \(K\) с этой гиперплоскостью. Тогда \[ \chi(K) = \chi(K_1) + \chi(K_2) + 2\chi(K_3) - 3\chi(K_4), \] поскольку каждая грань \(K\) либо лежит в секущей гиперплоскости (входит во все четыре \(\chi(K_i)\)), либо рассекается ей (образуя грань на единицу меньшей размерности в \(K_1\), \(K_2\) и \(K_4\), и внося отрицательный вклад в каждую из трёх характеристик), либо целиком лежит в одном из полупространств (и входит только в \(\chi(K_1)\) или \(\chi(K_2)\)).

\(K_1\) и \(K_2\) имеют меньшие двоичные разбиения, а \(K_3\) и \(K_4\) — меньшую размерность; по индукции у всех эйлерова характеристика равна нулю. Поэтому и \(\chi(K)=0\).

Это доказательство взято у Клейна и Роты, развивающих его в рамках более общей теории инвариантных мер на евклидовых пространствах. Благодарность также Робину Чапмену за помощь с объяснениями.

Пусть \(U^d\) — пространство функций из \(\mathbb{R}^d\) в \(\mathbb{R}\), а \(V^d\) — подпространство \(U^d\), порождённое характеристическими функциями компактных выпуклых множеств в \(\mathbb{R}^d\). Определим функцию \(\chi_d\), отображающую \(V^d\) в вещественные числа:

• Если \(d=1\), для любой функции \(f \in V^d\) положим \[ \operatorname{D} f(x) = f(x) - \lim_{y\to x^+} f(y), \] \[ \chi_1(f) = \sum_{x\in\mathbb{R}} \operatorname{D} f(x). \] (Эта сумма всегда имеет лишь конечное число ненулевых слагаемых.)

• Если \(d > 1\), разобьём координаты \(\mathbb{R}^d\) на группы из \(d-1\) и \(1\): \[ \mathbb{R}^d = \mathbb{R}^{d-1}\times\mathbb{R}. \] Любая точка \(\mathbb{R}^d\) представляется как пара \((x,z)\), где \(x \in \mathbb{R}^{d-1}\), \(z \in \mathbb{R}\). Для функции \(f \in V^d\) и числа \(z \in \mathbb{R}\) обозначим через \(f_z\) сужение \(f\) на \((d-1)\)-мерное сечение: \(f_z(x)=f(x,z)\), так что \(f_z \in V^{d-1}\). Тогда \[ \chi_d(f) = \sum_{z\in\mathbb{R}} \operatorname{D} \chi_{d-1}(f_z). \]

Поскольку \(\operatorname{D}\) и \(\sum\) линейны, \(\chi\) — линейная функция из \(V^d\) в \(\mathbb{R}\). Простой индукцией по размерности показывается, что для характеристической функции \(f\) компактного выпуклого множества \(K\) выполнено \(\chi(f)=1\): по индукции \(\chi(f_z)\) есть характеристическая функция замкнутого отрезка, и из определения следует, что \(\sum\operatorname{D}\chi(f_z) = 1\). Отсюда (и из того, что характеристические функции компактных выпуклых множеств образуют базис \(V^d\)) следует корректность определения \(\chi\) независимо от выбора координат в \(\mathbb{R}^d\).

Если \(g\) — характеристическая функция относительной внутренности многогранника \(K\), то \(g \in V^d\) (по включению-исключению граней младших размерностей) и аналогичная индукция показывает, что \(\chi(g)=(-1)^m\), где \(m\) — размерность \(K\): благодаря независимости \(\chi\) от системы координат можно считать \(m=d\). Каждое сечение \(K\) — многогранник, поэтому по индукции \(\chi(g_z)\) равно \((-1)^{m-1}\), умноженному на характеристическую функцию открытого интервала, а действие операторов \(\sum\) и \(\operatorname{D}\) домножает ещё на \(-1\).

Пусть теперь \(K\) — выпуклый многогранник. Вычислим \(\chi\) на его характеристической функции двумя способами, разбив \(K\) в объединение непересекающихся относительных внутренностей граней. По линейности \(\chi\) сумма значений на этих внутренностях равна значению на всём \(K\): \[ 1 = \sum (-1)^m, \] где суммирование — по всем граням \(K\) (включая сам \(K\)). Группируя грани по размерностям, получаем форму формулы Эйлера: \[ 1 = \sum_{i=0}^d (-1)^i f_i. \]

Это доказательство взято из статьи Джима Лоуренса 1997 года. Оно применимо к выпуклым многогранникам в \(\mathbb{R}^d\) и в некоторых отношениях напоминает доказательство через аддитивные инварианты.

Пусть \(\mathcal{A}\) — конечное расположение гиперплоскостей в \(\mathbb{R}^d\). Оно разбивает \(\mathbb{R}^d\) на грани: множества точек, лежащих на одном и том же наборе гиперплоскостей и по одну сторону от всех остальных. Лоуренс определяет \(\mathcal{A}\)-многогранник как произвольное объединение граней и функцию \(\chi\) на \(\mathcal{A}\)-многогранниках: для грани \(f\) полагается \(\chi(f)=(-1)^{\dim f}\), а для \(\mathcal{A}\)-многогранника \(P\), состоящего из граней \(f_i\), — \(\chi(P)=\sum\chi(f_i)\).

Нетрудно убедиться, что \(\chi(P)\) одинакова для всех расположений \(\mathcal{A}\), для которых \(P\) является \(\mathcal{A}\)-многогранником: добавление «лишней» гиперплоскости лишь разбивает некоторые грани на две грани той же размерности и одну грань на единицу меньшей размерности, что не меняет \(\chi\), а удаление — обратная операция. Следовательно, для любого непустого пересечения конечного числа открытых полупространств \(P\) выполнено \(\chi(P)=(-1)^{\dim P}\) (в качестве \(\mathcal{A}\) берутся граничные гиперплоскости полупространств, определяющих \(P\), для которых \(P\) — грань). В частности, из пересечения нуля полупространств получаем \(\chi(\mathbb{R}^d)=(-1)^d\). Кроме того, \(\chi\) аддитивна на непересекающихся объединениях.

Вычислим эйлерову характеристику замкнутого \(d\)-мерного выпуклого многогранника \(P\): вложим \(P\) в гиперплоскость, не проходящую через начало координат, в \(\mathbb{R}^{d+1}\), образуем бесконечный конус \(C\) из положительных скалярных кратных точек \(P\) и положим \(X(P)=\chi(C)\). Эта величина (рассматриваемая через расположение гиперплоскостей, проходящих через гиперграни конуса) включает слагаемое \((-1)^k\) для каждой \(k\)-мерной грани \(P\): \(1\) для пустой грани (вершина конуса), \(-1\) для вершин (лучи — рёбра конуса, одномерные грани расположения), и т. д.

По аддитивности, \[ X(P) = \chi(\mathbb{R}^{d+1}) - \chi(\mathbb{R}^{d+1}\setminus C) = (-1)^{d+1} - \chi(\cup H_i), \] где \(H_i\) — открытое полупространство, ограниченное \(i\)-й гиперплоскостью со стороны, противоположной \(C\). Первое слагаемое известно, а второе вычисляется по формуле включений-исключений: \[ \sum_{S\subset [1,n]} (-1)^{|S|} \chi\left(\cap_{i\in S} H_i\right), \] где сумма — по непустым подмножествам полупространств \(H_i\). Все такие пересечения непусты (содержат конус, дополнительный к \(C\)) и являются открытыми выпуклыми многогранниками, поэтому сумма упрощается: \[ \sum_{i=1}^n (-1)^i \binom{n}{i} (-1)^{d+1} = (-1)^{d+1}, \] что в точности компенсирует \(\chi(\mathbb{R}^{d+1})\), давая \(X(C)=0\).

Для фигуры \(S\) на плоскости обозначим через \(p_S(n)\) число точек с целочисленными координатами в копии \(S\), масштабированной с положительным целым множителем \(n\). В ряде простых случаев формула для \(p(n)\) легко вычисляется:

• Если \(S\) — одна целая точка, то \(p_S(n)=1\).

• Если \(S\) — открытый отрезок с целыми концами, содержащий \(k\) целых точек, то \(p_S(n)=(k+1)n-1\). Для замкнутого отрезка — \(p_S(n)=(k-1)n+1\).

• Если \(S\) — внутренность многоугольника с целочисленными вершинами, площадью \(A\) и \(k\) граничными точками, то по формуле Пика \(p_S(n)=An^2-(k/2)n+1\). Для замыкания такого многоугольника — \(p_S(n)=An^2+(k/2)n+1\).

Во всех этих случаях \(p\) — многочлен степени, равной размерности \(S\), и \(|p(0)|=1\).

Как и в доказательстве через формулу Пика, нарисуем планарный граф с целочисленными координатами на плоскости. Число целых точек, покрытых масштабированными копиями рисунка, можно подсчитать двумя способами: как \(p_S(n)\) для замкнутого многоугольника, ограниченного внешней гранью, и как сумму \(p_S(n)\) по всем вершинам, открытым рёбрам и внутренностям внутренних граней: \[ \sum_{v\in V} p_v(n) + \sum_{e\in E} p_{\operatorname{int}(e)}(n) + \sum_{f\in F} p_{\operatorname{int}(f)}(n) = p_{\operatorname{cl}(\text{внешняя грань})}(n) + p_{\operatorname{int}(\text{внешняя грань})}(n). \] (Слагаемое для внутренности внешней грани в правой части добавлено для компенсации этой грани в левой части, поскольку мы хотели суммировать только по внутренним граням, но сумма включает и все грани.)

Подставив \(n=0\), получаем: \[ \sum_{v\in V} p_v(0) + \sum_{e\in E} p_{\operatorname{int}(e)}(0) + \sum_{f\in F} p_{\operatorname{int}(f)}(0) = p_{\operatorname{cl}(\text{внешняя грань})}(0) + p_{\operatorname{int}(\text{внешняя грань})}(0). \] В левой части каждая вершина и грань вносят \(+1\), а каждое ребро — \(-1\); правая часть равна \(2\). Отсюда следует формула Эйлера.

Теорема Эрхарта–Макдональда позволяет заключить, что \(|p(0)|=1\) для относительно открытых выпуклых многогранников старших размерностей, что обобщает это доказательство на любой выпуклый многогранник в \(\mathbb{R}^d\) с целыми или рациональными координатами вершин (Бек и Робинс, теорема 5.2). Все многогранники в \(\mathbb{R}^3\) реализуемы с целочисленными координатами, но для старших размерностей это неверно.

Учитывая сходство названий «эйлеров обход» (замкнутый обход графа, проходящий по каждому ребру ровно один раз) и «формула Эйлера», удивительно, что глубокая связь между ними была обнаружена лишь недавно. Приведённое ниже доказательство основано на соотношении между повторениями вершин и числом граней в эйлеровых планарных графах, замеченном программой Red Burton — версией системы Graffiti для формулировки гипотез в теории графов.

Планарный граф \(G\) допускает эйлеров обход тогда и только тогда, когда степень каждой его вершины чётна. Для такого обхода обозначим через \(R\) число раз, когда обход достигает вершины, уже встреченной ранее. Например, для графа, состоящего из единственного цикла, повторяется только начальная вершина: \(R=1\). Как заметила система Red Burton, всегда \(F=R+1\): если рисовать рёбра в порядке обхода, вначале имеется одна грань, и каждая повторная вершина замыкает ещё одну грань. С другой стороны, \(R=E-V+1\), поскольку обход проходит \(E+1\) вершину от начала до конца, из которых \(V\) — неповторные. Приравнивая два выражения для \(R\), получаем формулу Эйлера — но только для эйлеровых графов.

Для произвольного планарного графа \(G\) проведём по две параллельные копии каждого ребра, разделённые узкой двусторонней гранью. Эта модификация не меняет \(V-E+F\), поскольку к числу рёбер и граней прибавляется одна и та же величина \(E\), взаимно компенсирующаяся в формуле. Полученный граф эйлеров, поэтому к нему применим аргумент о повторениях, дающий \(V-E+F=2\). То же самое верно и для исходного графа.

Идея доказательства формулы Эйлера через превращение произвольного планарного графа в эйлеров принадлежит Стефани Мэтью, студентке второго курса факультета химической инженерии Хьюстонского университета, работавшей под руководством Шимона Файтловича, который использовал эту идею для приведённого доказательства. Файтлович также описывает два варианта: в одном пары нечётных вершин последовательно соединяются дугой на плоскости, избегающей все вершины; в другом — удвоением путей в графе. Оба варианта используют факт, что в любом графе число вершин нечётной степени чётно, доказанный Эйлером.

Это доказательство взято у Глиненого (Hliněný). Оно проводится индукцией и доказывает, что для всех выпуклых многогранников \(P\) \[ \chi(P)=\sum_{i=0}^d (-1)^i f_i=1, \] где \(f_i\) — число \(i\)-мерных граней \(P\). Мы включаем \(f_d=1\) для всего многогранника, но не считаем пустое множество гранью.

Рассмотрим \((d-1)\)-мерную диаграмму Шлегеля данного \(d\)-мерного многогранника и выберем проекцию \(\pi\) из \(\mathbb{R}^{d-1}\) в \(\mathbb{R}^{d-2}\), направление которой находится в общем положении: все грани многогранника размерности до \(d-2\) проецируются в выпуклое множество той же размерности. Для гиперграни \(f\) многогранника и её диаграммы Шлегеля силуэтом \(f\) назовём те грани \(f\), которые проецируются в грани \(\pi(f)\).

Как и в доказательствах через электрический заряд и двойственный заряд, каждой грани многогранника приписывается заряд \(\pm 1\), равный её вкладу в эйлерову характеристику: \((-1)^i\) для грани размерности \(i\). Суммарный заряд — это \(\chi(P)\). Перераспределим заряд по гиперграням и просуммируем. Заряд перераспределяется так: выбирается базовая точка внутри грани в диаграмме Шлегеля (неважно где именно внутри), и половина заряда отправляется вверх, а половина — вниз, к двум гиперграням, расположенным непосредственно над и под базовой точкой в направлении проекции. Так перераспределяются все заряды, кроме заряда всего многогранника, который направляется на внешнюю гипергрань диаграммы Шлегеля.

Если \(f\) — внутренняя гипергрань диаграммы Шлегеля, она получает половину заряда от каждой своей грани, кроме граней силуэта, от которых не получает ничего. Также она получает дополнительную половину заряда от собственной базовой точки, поскольку обе половины заряда идут в \(f\), а не в другую гипергрань. Поэтому её вклад в суммарный перераспределённый заряд: \[ \frac12\Bigl(\chi(f)\pm 1\Bigr) - \frac12\Bigl(\chi\bigl(\pi(f)\bigr)\pm 1\Bigr) = \frac12(1\pm 1) - \frac12(1\pm 1) = 0, \] где дополнительный заряд \(\pm\tfrac12\) в части, связанной с силуэтом, соответствует тому, что \(\pi(f)\) не приходит от грани силуэта, но тем не менее учитывается в \(\chi\bigl(\pi(f)\bigr)\). Обе эйлеровы характеристики равны \(1\) по индукционной гипотезе (индукция по размерности). Для внешней гиперграни диаграммы Шлегеля аналогичное вычисление даёт другой результат: каждая грань силуэта вносит два полузаряда вместо нуля, а заряд от всего многогранника добавляет \(\mp 1\): \[ \frac12\Bigl(\chi(f)\pm 1\Bigr) + \frac12\Bigl(\chi\bigl(\pi(f)\bigr)\pm 1\Bigr) \mp 1 = \frac12 (1\pm 1) + \frac12 (1\pm 1) \mp 1 = 1. \] Перераспределённый заряд равен нулю для внутренних гиперграней и единице для внешней гиперграни, поэтому эйлерова характеристика, равная суммарному перераспределённому заряду, равна единице.

Глиненый далее описывает эквивалентную формулировку того же доказательства через проекции из двух выделенных точек в \(\mathbb{R}^d\), а не через проекцию диаграммы Шлегеля в \(\mathbb{R}^{d+1}\).