Перечисление помеченных колючих графов

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