Конструктивные и неконструктивные доказательства

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

В первом случае объект, существование которого доказывается, предъявляется в явном виде.

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

В решении приводятся оба варианта доказательства. Однако понятно, что с практической точки зрения ценнее конструктивный вариант.

#олимпиады #графы

Цветочный город (#117)