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

 Вершины  = 4

Области = 3

Линии = 6

 Вершины  = 6

Области = 1

Линии = 6

 Вершины  = 5

Области = 10

Линии= 6

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

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

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

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

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

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

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

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

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

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