A separating set also called a vertex cut, in a connected graph is a set of vertices whose deletion disconnects .
- In general it is the set of vertices that increase the number of components by .
A cut vertex is a separating set with only one element.
If is connected, its vertex connectivity, denoted is the size of the smallest separating set in .

It is the minimum number of vertices we need to delete to disconnect .

If , we say the graph is -connected

Menger’s Theorem

Can be thought of as a special case of the Max-Flow Min-Cut Theorem.
- Intuition: Consider a weighted graph. For each edge with weight , incident to delete it and create new edges. Edge independent / Vertex independent paths now correspond flows in this flow network, while Edge / Vertex cuts now correspond to cuts in the flow network.
(Wilson 28.1) Menger’s Theorem (Vertex Version) - the maximum number of vertex disjoint paths connected two distinct vertices and of a connected graph is equal to the minimum number of edges in a -vertex cut.
(Wilson 28.6) Menger’s Theorem implies Hall’s Theorem
(Wilson 28.3) - A graph is -connected if and only if any two distinct vertices of are connected by at least -edge disjoint paths
- Proof: Follows from Menger’s Theorem
(Wilson 28.4) - A graph with at least vertices is -connected if and only if any two distinct vertices of are connected by at least -vertex disjoint paths
- Proof: Follows from Menger’s Theorem
(Wilson 28.5) The maximum number of arc-disjoint paths from to in a digraph is equal to the minimum number of arcs in a -disconnecting set.

Fragments and Atoms

A fragment of graph is a subset such that and . An atom of is a fragment that contains the minimum number of vertices (it must be connected).
- Intuition: Consider the minimum vertex cut. It will separate the graph into two components. The components are the fragments. The vertex cut, therefore, lies in the boundary of both fragments.
For any fragment
(Godsil 3.4.3) Let be fragments of . Then
(Godsil 3.4.4) Let be a graph on vertices with connectivity . Suppose and are fragments of such that . If then is a fragment.
- (Godsil 3.4.4.1) Equality holds in the above if and only if .
- (Godsil 3.4.4.2)
- (Godsil 3.4.4.3)
- (Godsil 3.4.4.4)
(Godsil 3.4.5) If is an atom and a fragment of then is a subset of exactly one of and
(Godsil e3.20) If is an atom and a fragment of such that , then .
- Proof: Let We have Computing the size, this is equivalent to And by minimality of . Therefore
We get . By atomicity, . Finally, we note that

This gives us which completes the proof.