Объединение графов и компоненты связности. Оценка числа рёбер через число вершин и число компонентов связности. Вершинная и рёберная связность: мосты и блоки, меры связности.

Напомним, что если граф G состоит из одной компоненты связности, (то есть k(G) = 1), то он называется связным.

В связном графе любые две вершины соединены (простой) цепью.

Теорема: Граф связен тогда и только тогда, когда его нельзя представить в виде объединения двух графов.

Рассмотрим граф: