Индукция в графах и теорема Турана

Будем считать, что в некоторых вершинах графа может быть целое отрицательное количество монет, но суммарное количество монет равно Докажем задачу индукцией по

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