Две вершины в графе называются связным, если существует соединяющая их простая цепь. Граф называется связным, если все его вершины связны.
Теорема. Граф связен тогда и только тогда, когда его нельзя представить в виде объединения двух графов.
Пусть G(V,E) – связный граф, u и v – две его несмежные вершины. Две цепи < u, v > называются вершинно-непересекающимися, если у них нет общих вершин, отличных от u и v.
Теорема (Менгера). Пусть u иv – несмежные вершины в графе G. Наименьшее число вершин в множестве, разделяющем u иv равно наибольшему числу вершинно-непересекающихся простых <u,v>-цепей:
max|P(u,v) | = min|S(u,v)|