Vertex connectivity

Vertex connectivity $\kappa (G)$ is the smallest number of vertices whose deletion disconnects a nontrivial graph or reduces it to one vertex.

For a specified set $S$ of vertices, a rooted separation is a pair $(A,B)$ with $A\cup B=V(G)$, $S\subseteq A$, and no edges between $A\setminus B$ and $B\setminus A$. Its order is $|A\cap B|$. It avoids a branch set $C$ when $A\cap C=\varnothing$. A graph with vertex connectivity at least $|S|$ has no rooted separation of order below $|S|$ avoiding a nonempty branch set: both sides of such a separation would be nonempty after deleting its separator.

A graph with more than $k$ vertices is $k$-connected when deleting fewer than $k$ vertices always leaves it connected, equivalently when its vertex connectivity is at least $k$.

A $k$-connected graph has a cycle of length at least $\min \{|G|,2k\}$.

A component outside a longest cycle has at least $k$ attachment vertices in a $k$-connected graph, and no two attachments are consecutive, forcing cycle length at least $2k$.

A graph is 3-connected when it has at least four vertices and remains connected after deletion of any two vertices.