Сап, математач! Кто-нибудь шарит в графах? Нужно понять, как доказать, что минимальное рёберное покрытие имеет мощность не более чем ND/(D+1), где N - число вершин, а D - максимальная степень вершины. Предполагается, что в графе нет изолированных вершин.
Пока в голову приходит только то, что можно взять вершину, имеющую максимальную степень, и в покрытие включить все инцидентные ей рёбра, тем самым покрыв D+1 вершину D рёбрами, затем исключить все покрытые вершины из графа и продолжить этот процесс, пока граф не опустеет. Но проблема в том, что в процессе такого удаления частей графа могут появиться изолированные вершины, которые в результате останутся непокрытыми.