О локальной структуре 9 и 10-связных графов

Р. Халин в своей статье (в “Recent Progress in Combinatorics”, Academic Press, 1969) сформулировал задача о нахождении наибольшей константы $c_k$, такой, что количество вершин степени $k$ в минимальном и минимальном по стягиванию $k$-связном графе $G$ равно по крайней мере $c_k|G|$. Двадцатью годами позже Н. Мартиновым и, независимо, М. Фонтэ была найдена константа $c_4$ ($c_4=1$).
В этой статье изучается локальная структура минимального и минимального по стягиванию $k$-связного графа и доказывается, что $c_k\geq\frac12$ (для $k=9,10$). Этот результат продлевает последовательность $c_k$, для которых доказана нижняя оценка $\frac12$ до $k=6,7,8,9,10$. Библ. – 18 назв.