Опр: 2 вершины в графе связаны,если 
соедин. их простая цепь. Граф наз. связ., если 
пары различ. вершин соединяющий их путь. Отношение связности явл. эквивалентностью.
Классы эквивалентности по отношению к связности назыв. компонентами свяности графов K(G).
Граф явл. связ. тогда и только тогда,когда К(G)=1 и несвяз. K(G)˃1.
Граф имеющий n-вершин, m-ребер, k-компонент связ-ти обозн. (n,m,k)-граф.
Вершина графа наз.точкой сочленения, если ее удаление удваивает число K(G).
Разрезающим мн-вом ребер графа наз-ся мн-во ребер удаления кот-го из графа приводит к увеличению числа K(G).
Мин. по включению разрезающее мн-во ребер наз. разрезом.
Мост графа- ребро являющееся одноэлементным разрезом.
Лемма о рукопожатиях и ее следствие.
Теорема: Сумма степеней всех вершин графа равна удвоенному числу ребер.
Док-во: Каждое ребро дает вклад = 2 при подсчете суммы степеней всех вершин.
Следствие.
В любом графе число вершин нечетной степени четно.
