Построение графа с указанными величинами вершинной и рёберной связностей и наименьшей из степеней вершин

Даны величины $\kappa$ , $\lambda$ , $\delta$ — это, соответственно, вершинная связность, рёберная связность и наименьшая из степеней вершин графа. Требуется построить граф, который бы обладал указанными значениями, или сказать, что такого графа не существует.

Соотношение Уитни

Соотношение Уитни (Whitney) (1932 г.) между рёберной связностью $\lambda$ , вершинной связностью $\kappa$ и наименьшей из степеней вершин $\delta$ :

$\kappa \le \lambda \le \delta.$

Докажем это утверждение.

Докажем сначала первое неравенство: $\kappa \le \lambda$ . Рассмотрим этот набор из $\lambda$ рёбер, делающих граф несвязным. Если мы возьмём от каждого из этих ребёр по одному концу (любому из двух) и удалим из графа, то тем самым с помощью $\le \lambda$ удалённых вершин (поскольку одна и та же вершина могла встретиться дважды) мы сделаем граф несвязным. Таким образом, $\kappa \le \lambda$ .

Докажем второе неравенство: $\lambda \le \delta$ . Рассмотрим вершину минимальной степени, тогда мы можем удалить все $\delta$ смежных с ней рёбер и тем самым отделить эту вершину от всего остального графа. Следовательно, $\lambda \le \delta$ .

Интересно, что неравенство Уитни нельзя улучшить: т.е. для любых троек чисел, удовлетворяющих этому неравенству, существует хотя бы один соответствующий граф. Это мы докажем конструктивно, показав, как строятся соответствующие графы.

Решение

Проверим, удовлетворяют ли данные числа $\kappa$ , $\lambda$ и $\delta$ соотношению Уитни. Если нет, то ответа не существует.

В противном случае, построим сам граф. Он будет состоять из $2 (\delta + 1)$ вершин, причём первые $\delta + 1$ вершины образуют полносвязный подграф, и вторые $\delta + 1$ вершины также образуют полносвязный подграф. Кроме того, соединим эти две части $\lambda$ рёбрами так, чтобы в первой части эти рёбра были смежны $\lambda$ вершинам, а в другой части — $\kappa$ вершинам. Легко убедиться в том, что полученный граф будет обладать необходимыми характеристиками.