Подвешивание, ранжирование, упорядочивание в графах

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

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

Действительно, все рёбра, выходящие из вершин с номерами от до делятся на два типа:

идущие в вершины с номерами от до — таких не болыше

идущие в вершины с номерами от до — таких не больше но каждое мы можем посчитать по два раза.

В задаче нас спрашивают, существует ли граф со степенями вершин Предположим, что он существует, и воспользуемся доказанным утверждением для первых пяти вершин:

противоречие.