Подобные рассуждения называют «доказательством по индукции». Это стандартный метод доказательства наиболее формализованных формулировок, и логику, на которой он основан, можно сделать строгой. Предложенная Кейли стратегия доказательства становится более понятной, если переформулировать ее с использованием логически эквивалентной концепции минимального контрпримера. В данном контексте контрпримером можно считать любую гипотетическую карту, которую невозможно раскрасить в четыре краски. Такая карта будет минимальной, если любую меньшую карту (т. е. карту с меньшим числом областей) можно раскрасить нужным образом. Если хотя бы один контрпример существует, то должен существовать и минимальный контрпример: чтобы его найти, нужно просто взять контрпример с минимальным возможным числом областей. Поэтому если минимального контрпримера не существует, то контрпримеров не существует вообще. А если их нет, то теорема о четырех красках верна.

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

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

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

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