k-Connected Graph¶

k-Connected Graph¶

A graph is called k-connected if it has more than k vertices, and removing fewer than k vertices does not disconnect the graph—with k being the largest possible such value. It is denoted as \(\kappa (G)\).

Another definition for this concept exists: the minimum number of vertices whose removal disconnects the graph. However, this definition has an issue with complete graphs. Note that you can never disconnect a complete graph by removing any number of vertices; you can only reduce it to a single vertex. By adjusting the second definition slightly, we can correct it:

• The minimum number of vertices whose removal disconnects the graph or reduces it to a single vertex.

\(\kappa (u,v)\) is defined as the minimum number of vertices whose removal disconnects the vertices u and v (i.e., places them in two separate components).

k-edge-connected graph¶

Similar to the definition of a k-connected graph, this definition applies to edges instead of vertices.

An edge k-connected graph is a graph that can be disconnected or reduced to an isolated vertex by removing at least k edges. This is denoted by \(\kappa^{\prime}(G)\). Note that this value can be zero. If the graph is connected and contains a bridge (edge cut), the value becomes one.

Additionally, \(\kappa^{\prime}(u,v)\) is defined as the minimum number of edges whose removal severs the connection between vertices u and v, placing them in two separate components.

Menger's Theorem¶

Several paths between vertices u and v are called disjoint if these paths share no common vertices except the two vertices u and v. We can now state that the minimum number of vertices whose removal disconnects the communication between vertices u and v is equal to the maximum number of disjoint paths between these two vertices.

The same theorem applies to edges as well, stating that the minimum number of edges whose removal disconnects the communication between two vertices is equal to the maximum number of edge-disjoint paths between the two vertices.