Числом вершинной связности (или просто числом связности)  графа  называется число, равное наименьшему числу вершин, удаление которых приводит к несвязному или одновершинному графу.

Можно нарушить связность графа, удаляя некоторые его ребра (дуги).

Числом реберной связности  графа  называется число, равное наименьшему числу ребер, удаление которых приводит к несвязному графу. Число реберной связности одновершинного графа полагается равным нулю.