Course contentsShow
← Mathematics
Lesson 2662 of 3,12153. Graph TheoryFree lesson

Vertex Connectivity

Define vertex connectivity and k-connected graphs; understand minimum vertex cuts and graph robustness.

Vertex Connectivity

You'll learn how to measure a graph's resilience to vertex removal and what makes a graph k-connected.

What Is Vertex Connectivity?

Vertex connectivity measures how "robust" a graph is—specifically, how many vertices you must remove to disconnect it (or reduce it to a single vertex). It tells us the minimum number of vertices whose removal would break the graph into separate pieces.

Think of a communication network: vertex connectivity tells you the minimum number of nodes that must fail before the network splits into isolated groups. A higher vertex connectivity means a more reliable, fault-tolerant network.

Formal Definition

The vertex connectivity (denoted κ(G)) of a connected graph G is the minimum number of vertices that must be removed to either:

  • Disconnect the graph, or
  • Reduce it to a single vertex (for complete graphs)

A graph is called k-connected if its vertex connectivity is at least k. In other words, you need to remove at least k vertices to disconnect it.

Minimum Vertex Cuts

A vertex cut (or separating set) is a set of vertices whose removal increases the number of connected components. The smallest such set is a minimum vertex cut, and its size equals κ(G).

Example: In a graph that's a simple path (v₁—v₂—v₃—v₄), removing just v₂ or v₃ disconnects it, so κ(G) = 1.

Graph Robustness

  • κ(G) = 0: Graph is disconnected (or has only one vertex)
  • κ(G) = 1: Graph has at least one cut vertex
  • κ(G) ≥ 2: Graph is 2-connected; no single vertex failure breaks it
  • Higher κ means greater robustness

Key Takeaway: Vertex connectivity κ(G) is the size of the smallest vertex cut, measuring how many vertices must fail to disconnect a graph; a graph is k-connected if κ(G) ≥ k.