Об оптимальности реализаций графов с заданными мерами связности

Две основные меры связности графа  — вершинная $k$ и рёберная $\lambda$  — связаны с минимальной степенью вершины $\delta$ графа известным соотношением Уитни: $k {\leq} \lambda {\leq} \delta$. Г. Чартрэнд и Ф. Харари доказали, что этот результат не улучшаем в том смысле, что для любых натуральных чисел $a, b, c$, таких, что $ a \leq b \leq c$, можно построить граф, у которого $k = a$, $\lambda = b$, $\delta = c$. В доказательстве Чартрэнда и Харари предлагается граф с числом вершин $2(c + 1)$ и числом рёбер $c(c + 1) + b$. В данной работе рассматривается вопрос построения соответствующей реализации с наименьшим возможным числом вершин и рёбер.