Аннотация:
Граф называется $k$-связным, если он имеет хотя бы $k+1$ вершину и остается связным при удалении любых своих $k-1$ вершин. $k$-связный граф называется минимальным, если при удалении любого его ребра граф перестает быть $k$-связным. В. Мадер доказал, что минимальный $k$-связный граф на $n$ вершинах содержит как минимум $\frac{(k-1)n+2k}{2k-1}$ вершин степени $k$. В работе доказывается, что любой минимальный $k$-связный граф, содержащий наименьшее возможное число вершин степени $k$, имеет вид $G_{k,T}$, где $T$ – дерево, степени вершин которого не превосходят $k+1$. Граф $G_{k,T}$ строится из $k$ непересекающихся копий дерева $T$. Для каждой вешины $a$ дерева $T$ обозначим через $a_1,\dots,a_k$ соответствующие ей вершины копий. Если вершина $a$ имеет степень $j$ в дереве $T$, то добавляются $k+1-j$ новых вершин степени $k$, смежных с $\{a_1,\dots,a_k\}$. Библ. – 10 назв.