Связныйнеориентированный граф G –любая пара вершин соединена маршрутом (либо простой цепью) в G.
Компонента связности или компонента графа G –максимальный связный подграф графа G.
Две вершины 
и 
называются связаннымив графе G, если в графе G существует маршрут между этими двумя вершинами. Вершина считается связанной сама с собой.
Связный граф состоит из одной компоненты связности.
Число вершинной связности χ(G) –наименьшее число вершин, удаление которых приводит к несвязному или одновершинному графу.
Например: 
Число реберной связности l(G) –наименьшее число рёбер, удаление которых приводит к несвязному или одновершинному графу.
Например: 
Считается, что 
.
Точка сочленения (разделяющая вершина) –вершина v графа G, удаление которой увеличивает количество компонент связности графа G.
Мост –ребро, удаление которого приводит к увеличению числа компонент связности.
Неразделимый граф –граф без точек сочленения.
Блок –максимальный неразделимый подграф графа G.
