图论与组合：连通性 / CutsAndConnectivity

分割集 (separating set)/ 点割 (vertex cut): 点集 $S\subset V(G)$, 满足 $G-S$ 的不连通或只有一个顶点.

连通度 $\kappa(G)$: 点割集合大小的最小值.

如果图 $G$ 的连通度至少为 k, 则称它是 k-连通的.

Harary graph $H_{k,n}$, $V=\Z_n$.

• $k=2t,\ \forall x,y\in V$, $x\leftrightarrow y \Leftrightarrow x-y\in\{\pm 1,\pm 2,\cdots,\pm t\}$.
• $k=2t+1\wedge n=2m$, $\forall x,y\in V$, $x\leftrightarrow y \Leftrightarrow x-y\in\{\pm 1,\pm 2,\cdots,\pm t,m\}$.
• $k=2t+1\wedge n=2m+1$, $E(H_{k,n})=E(H_{k-1,n})\cup\{i\leftrightarrow i+m|0\leqslant i\leqslant m\}$.