Некоторые критерии связности в неориентированных графах:

• Две вершины называются связанными, если в графе существует путь между ними. 1 Вершина считается связанной сама с собой. 2
• Неориентированный граф называется связным, если имеется путь между любыми двумя его различными вершинами. 3
• Компонентой связности называется максимальный связный подграф графа. 25 Связный граф состоит из одной компоненты связности, в противном случае он называется несвязным. 1
• Вершина графа называется точкой сочленения, если её удаление (вместе с инцидентными ей рёбрами) увеличивает число компонент связности графа. 4
• Ребро графа называется мостом, если его удаление увеличивает число компонент связности графа. 4