Таким образом, заключил Эйлер, какой бы ни была сеть мостов, обойти все мосты, побывав на каждом по одному и только одному разу, можно только в том случае, если все части города соединены с другими четным числом мостов или если ровно две части города соединены с другими частями нечетным числом мостов. В Кенигсберге город подразделяется всего на четыре части, — и все они соединены с другими частями нечетным числом мостов. На схеме Кенигсберга три точки принадлежат трем линиям, а одна — пяти линиям. Тем самым Эйлер не только сумел объяснить, почему все семь кёнигсбергских мостов невозможно обойти, побывав на каждом один и только один раз, но и придумал правило, применимое к любой сети мостов в любом городе мира. Рассуждения Эйлера отличаются замечательной красотой. По-видимому, такого сорта логические задачи Эйлер и любил решать за обедом.

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

V — R + L = 1,

где

V — число вершин (узлов, или пересечений) в графе,

R — число линий (ребер) в графе,

L — число замкнутых областей в графе.

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

Вершины = 4

Области = 3

Линии = 6

Вершины = 6

Области = 1

Линии = 6

Вершины = 5

Области = 10

Линии= 6

Рис. 9. Различные графы, удовлетворяющие формуле Эйлера

Рис. 10. Эйлер доказал свою формулу для графов, продемонстрировав, что она выполняется для простейшего графа, а затем показав, что формула остается верной при любых «дополнениях» к единственной вершине

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

Свое доказательство Эйлер начал с простейшего из графов — с графа, состоящего из одной единственной вершины (рис. 10а ). Ясно, что для такого графа формула Эйлера верна: имеется всего одна вершина, линий и областей нет, поэтому

V

+ R — L = 1 + 0–0 = 1

.

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

Во-первых, рассмотрим случай, когда дополнительная линия соединяет существующую вершину с самой собой. Как видно из рис. 10б , при добавлении линии в этом случае добавляется также новая область. Следовательно, формула Эйлера для графов остается в силе, так как добавление одной области (+) компенсируется добавлением одной линии (—). При добавлении новых линий того же типа формула Эйлера для графов также останется в силе, так как каждая новая линия порождает новую область.

Во-вторых, рассмотрим, что произойдет, если дополнительная линия соединит существующую вершину с новой вершиной, как на рис. 10в . И в этом случае формула Эйлера остается в силе, так как новая вершина (+) компенсирует новую линию (—). При добавлении новых линий того же типа формула Эйлера также остается в силе, поскольку каждая дополнительная линия рассматриваемого типа заканчивается в новой вершине.

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