Дан граф

. Пронумеруем все вершины случайным образом числами от

до

, назовем вершину экстремальной, если ее номер больше, чем номера всех соседних с ней вершин. Среднее количество экстремальных вершин по всем расстановкам обозначим

.
Какое минимально возможное значение

по всем графам

, содержащим ровно

вершин и

ребер?
Я начал с того что попытался выяснить чему равна

для произвольного графа

. Пусть

, если для

-ой перестановки

-ая вершина является экстремальной, иначе

. Тогда

, от перестановки слагаемых сумма не меняется, поэтому

. Теперь рассмотрим

,

зависит от количества соседей вершины под номером

, обозначим его

.
Посчитаем количество нумераций таких, что номер вершины

больше номера любого из ее соседей: номер вершины

обязан быть больше количества ее соседей, поэтому рассмотрим случай когда номер вершины

равен

, тогда количество подходящих нумераций ее соседей равно

, далее если номер вершины

равен

, тогда количество подходящих нумераций ее соседей равно

, при этом каждой такой нумерации соответствует

нумераций остальных вершин, тогда

, ну а дальше нифига не понятно что с этим чудом делать, кажется что вообще не туда забрел
