connectivity 와 vertex 갯수의 관계, connectivity 와 edge-connectivity, minimum degree에 대해 알아보자.
$\kappa(G) \leq n(G)-1$
$v_1,v_2,...,v_{n(G)-1} \in V(G) $ 라고 하자. 그리고 $S=\{ v_1,v_2,...,v_{n(G)-1} \}$라 합시다. $G-S$는 vertex 하나만 갖고 있습니다. $G$는 loop를 갖고 있지 않기 때문에 $G-S$는 disconnected 입니다. 따라서 $\kappa(G) \leq n(G) -1$
$G$ 가 simple graph 일 때 $\kappa(G) \leq \kappa \prime (G) \leq \delta(G)$인 이유
$[S, \bar{S} ]$를 가장 작은 edge cut 이라고 합시다. 이럴 때 경우가 두가지 생깁니다.
첫번째 경우: 모든 $x\in S$에 대하여 $N(x) \cap \bar{S} =\bar{S}$
이럴 경우 $|[S, \bar{S}] = |S| |\bar{S}| = |S| ( n(G)-|S|)$입니다. 그러면 $[S,\bar{S}] \geq n-1 \geq \kappa(G)$입니다. 따라서 $\kappa(G) \leq \kappa\prime(G)$ 입니다.
두번째 경우: $N(x) \cap \bar{S}$이 $\bar{S}$의 proper subset 이 되는 $x \in S$가 존재하는 경우
이럴 경우에는 $y \in \bar{S}$가 존재하여 $x$와 $y$가 adjacent 하지 않는 경우가 생깁니다. $T=(N(x) \cap \bar{S}) \cup ((S-x) \cap N(\bar{S}))$이라 하자. $P$를 그래프 $G$에서 $xy$ path 라고 합시다. 이 P는 x에서 시작하므로 P안에는 x에서 $\bar{S}$로 가는 edge가 있거나 x와 adjacent 하면서 $\bar{S}$와 adjacent 한 edge가 있어야 한다. 즉 $P$는 $T$를 통과한다. 따라서 $G-T$에는 $xy$ path 가 존재하지 안흔다. $|T| \geq \kappa(G)$이다. 모든 $u \in T$에 대하여 두가지 경우가 존재한다.
1. $ux$가 존재하는 $u\in N(x) \cap \bar{S}$가 존재하는 경우
2. $u \in (S-x) \cap N(\bar{S})$,$z\in \bar{S}$가 존재하여 $uz$가 존재하는 경우
이러한 모든 엣지는 다 distinct 하다. 따라서 $|[S,\bar{S}]| \geq |T| \geq \kappa(G)$ 이고 $\kappa\prime(G) \geq \kappa(G)$입니다.