[Graph Theory] Connectivity, path, and cycle

5.4. Connectivity and independent paths

 

Definition

$x,y$-separating set: $S \subseteq V(G)-\{x, y\}$ 이고, $xy \notin E(G)$ 일 떄 $G-S$에 $x,y$-path가 없게 하는 vertex set. $x$에서 $y$로 가는 길을 끊으려면 필요한 vertex 모임

$\kappa(x, y)$: minimum size of the $x,y$-seperating set. $x,y$ 로 가는 길 막으려면 최소 몇 개 vertex 뽑아야 함?

Paths from x to y are independent: share no internal vertex , vertex 안겹치게 x에서 y로 가는 경로들

$\lambda(x, y)$: maximum number of x,y-paths. vertex 안겹치게 x에서 y로 갈 수 있는 경로가 최대 몇개?

 

Fact.

$\kappa(x,y) \geq \lambda(x,y)$.

$\kappa(G) = min \{\kappa(x,y): xy \notin E(G)\}$.

 

Definition

$X,Y$-path: $X$에서 $Y$로 가는 path. subset to subset 으로 가는 path.

strict $X,Y$-path: X and Y를 딱 끝에서만 만남. X에서 Y로. 하지만 중간에 양끝에 들르는 거 없이.

$X,Y$-barrier: $G-Z$가 $X,Y$-path 가 없게하는 vertex set $Z$. 두 그룹 사이 path를 끊어버릴 수 있는 vertex set.

$X,Y$-link: a set of pairwise disjoint strict $X,Y$-paths. strict 한 path 들의 모임.

 

$X,Y$ 본인들도 $X,Y$-barrier에 포함됨.

 

Theorem <Pym>

digraph $G$,

최소 사이즈의 $X,Y$-barrier 은 최대 사이즈의 $X,Y$-link 와 같다.

$X,Y$를 끊으려면 필요한 vertex의 최소 갯수랑 $X,Y$사이를 연결해주는 path의 최대 갯수가 같다.

$\textit{Proof}$

$|V(G) + |E(G)|$ 에다가 induction 을 써보자. $G$ 가 vertex 1개 짜리면 일단 확실하고, 

이제 $k$가 $X,Y$-barrier 의 최소 사이즈라고 해보자.

 

Case1. $G$ 가 k짜리 $X,Y$-barrier $Z$ 를 갖고 있는데, $X$도, $Y$도 아니다.

$Z$가 $X$랑 $Y$사이 길을 다 막아버리니, 모든 $X,Y$ path들은 $Z$랑 겹친다.

그러니까 $X,Z$의 strict path 랑 $Y,Z$ strict path 는 안겹친다. 얘들을 $G_1$, $G_2$라고 하자.

이러면 $V(G_1) \cap V(G_2) = Z$다. 일단 $G_1$이건 $G_2$건, $G$보다는 작다.

$G_1$의 모든 $X, Z$ barrier 는 $X,Y$ barrier에 포함되니까 $G_1$은 $X,Z$ barrier 로 $k-1$개보다 많이 가질 수는 없다. 

여기에 induction 쓰면 $G-1$은$k$개 짜리 $X, Z$ link 를 가진다. <???>

같은 의미로 $G_2$도 $k$개짜리 $Y, Z$ link를 가져서 둘이 합치면 $k$개짜리 $X, Y$-link가 된다.

 

Case2.$X, Y$ 말고는 $k$짜리 $X, Y$ barrier를 못찾았다.

이러면 일단 $|X|=k$라고 두자. 만약 $X \subseteq Y$라면 이거는 길이 0짜리 link들로 $k$개 완성이다.

그게 아니면 $x \in X-Y$인 x를 보자.

$X-\{x\}$ 는 $X$가 $Y$로 가는 걸 못막으니까 $G-(X-\{x\})$ 는 strict $x,Y$ path를 가진다. <???>

이게 $w \notin X$ 에서 연결된 edge $xw$에서 시작된다.

그러면 $G' = G-xw$ 이고, $Z'$이 $G'$의 smallest $X,Y$-barrier라고 하자.

만약 $|Z'| \geq k$라면, induction hypothesis 는 $G'$에 k짜리 $X,Y$ link가 있음을 준다. $G$에서도 마찬가지 <???>

만약 $|Z'| < k$라면, $Z'$을 피해가는 $X,Y$-path 가 $G$중에 있는 거다. 그 path는 모두 $xw$를 이용한다는 뜻.

그러니까 $Z' \cup \{x\}$랑 $Z' \cup \{w\}$가 $G$의 $X,Y$ barrier 다. 그 set은 사이즈가 최대 $k$니까, Case 2 의 hpothesis 가 $Z' \cup \{x\} = X$ 라는 뜻이고, $Z' \cup \{w\}=Y$라는 뜻이다.

1-vertex path in $Z'$이랑 길이 1짜리 $x,w$ path 가 $X,Y$-link다.

 

Definition

$\kappa'(x,y)$: $x$랑 $y$를 uncreachable하게 하는 최소한의 edge 갯수. x,y 떼어놓으려면 잘라야하는 최소 edge 갯수

$\lambda'(x,y)$: pairwise edge-disjoint $x,y$-paths의 최대 갯수. edge가 안겹치는 $x,y$ path 갯수 중 최대한.

line graph <$L(G)$>: $G$의 edge 들이 vertex가 되는 graph 인데, $ef \in E(L(G))$ when $e, f \in E(G)$ with $e = uv$ and $f = vw$. $G$의 edge를 vertex로, vertex 공유 여부를 edge로 바꾼 그래프.

Line graph of a digraph: 다 똑같은데 edge being ordered pairs.

 

Theorem <Menger>

graph 또는 multigraph 또는 digraph에서

$\kappa(x,y) = \lambda(x,y)$ when $xy \notin E(G)$ and $\kappa'(x,y) = \lambda'(x,y)$ always.

끊으려면 뽑아야하는 최소 vertex 갯수는 안겹치는 최다 path 갯수. 끊으려면 잘라야 하는 최소 edge 갯수 = 안겹치는 최다 path 갯수.

$\textit{Proof}$

$X=N(x)$, $Y = N(y)$거나 $X = N^+(x)$, $Y = N^-(y)$ 로 해서 Pym's theorem 쓰면 됨.

 

Theorem. <Menger's theorem>

G는 k-connected $\Leftrightarrow$ $\lambda(x,y) \geq k$
G는 k-edge connected $\Leftrightarrow$ $\lambda'(x,y) \geq k$

임의의 두 vertex에서 찾을 수 있는 최다 path의 갯수랑 connectedness는 연관되어있다.

 

Lemma

edge를 자르는건 connectivity 를 최대한 1 줄인다.

edge를 암만 잘라봐야 줄일 수 있는 connectivity 는 1이다.

$\textit{Proof}$

$xy \in E(G)$ 이고, $\kappa(G-xy) < \kappa(G)$라고 치자. 

이러면 $G-xy-S$가 disconnected 되려면 vertex set $S$ 는 사이즈가 최대 $\kappa(G)-1$이다. <???>

$G-S$는 connected 니까, $xy$가 [$X,Y$] 의 유일한 edge cut이다. $x \in X, y \in Y$

만약 $|X| \geq 2$거나 $|Y| \geq 2$면 $S \cup \{x\}$ or $S \cup \{y\}$가 $G$를 seperates 한다.

그게 아니면 $|S| = |V(G)|-2$니까,

어쨌건 $|S| \geq \kappa(G)-1$이다.

 

$\textit{Proof of Theorem}$

$\kappa'(G) = min_{x,y \in V(G)}\kappa'(x,y)$ 니까, Menger's theorem 의 edge-connectivity 는 해결.

connectivity 파트에서 $\Leftarrow$는, 우선 이전의 Menger theorem에서 $\kappa(x,y) = \lambda(x,y)$이다. <???>

$\Righrarrow$는 $\lambda(x,y) \geq \kappa(G)$ for $xy \in E(G)$ 임을 보여야 함. $xy$는 $x,y$-path에서 유일하므로

$\lambda_G(x,y) = 1+\lambda_{G-xy}(x,y) = 1+\kappa_{G-xy}(x,y) \geq 1+\kappa(G-xy) \leq \kappa(G)$

<??????????>

 

Definition

$x,U$-fan of size k: set of $k$ paths from $x$ to $U$, x랑 $U$는 endpoint만 포함. for $x \in V(G)$ and $U \subseteq V(G)$. $x$에서 뿜어져 나오는 path의 $k$개짜리 모음.

 

Lemma <Expansion lemma>

$G$ 는 k-connected이고, $G'$은 $G$ 중에 $k$개의 neighbor를 가진 vertex $y$를 추가 $\Rightarrow$ G'은 k-connected

원래 그래프에서 $k$개 뽑아다 새로 소개시켜주면서 한 명 덧붙여도 여전히 $k$-connected다.

 

Lemma <Fan lemma>

$k$개보다 vertex가 많을 때,

k-connected $\Leftrightarrow$ size $k$짜리 $x,U$-fan 이 있음.

$k$개 $x,U$-fan 이 있다면 $k-connected$다.|

$\textit{Proof}$

$G$ 중에서 $k$명 소개시켜줘서 한 명 붙인 $G'$을 생각하자.

$G$가 $k$-connected 니까 $G'$ 도 $k$-connected 다 by expansion lemma.

$G'$에는 $k$개의 independent $x,y$ path가 있다 by Menger's theorem.

중간에 딱 끊으면 $U$가 나온다.

만약 $G$가 k-connected가 아니라면, $S$가 k-1개의 separating set을 가진다고 하자. (vertex가 $k$개보다 많으시다잖아)

$G-S$로 잘린 component에서 각각 $x, y$를 골라서 $U = S \cup \{y\}$가 되게 하면,

size$k$짜리 $x,U$-fan 은 절대 없는거다. 왜냐하면 x,y path 들이 죄다 $S$에서 겹치니까.

 

 

5.5. Cycles

 

Theorem <Dirac>

$k \geq 2$일 떄,

k-connected graph 의 $k$ 개의 vertex 들은 cycle 위에 있다.

k-connected면 cycle 위에 있는 $k$개의 vertex들을 찾을 수 있다.

$\textit{Proof}$

Induction on $k$. $k=2$일 떄, x,y의 independent paths 들은 Menger theorem 으로 인해 $x,y$를 포함하는 cycle을 만든다.

$k>2$일 때, $k$-connected 는 $(k-1)$-connected 이기도 하니까,

$G$는 $k$개의 vertex로 이루어진 set $S$에 대해서 $S-\{x\}$를 통과하는 cycle $C$를 가진다. <???>

만약 $|V(C)| = k-1$이라면, $x,V(C)$-fan 은 $C$를 끝에서만 만나는 paths 들을 준다. 여기에서 나오는 path 들 중 2개를 고르면 $x$를 포함한 augment 를 얻을 수 있다.

만약 $|V(C)| \geq k$라면, $k$짜리  $x,V(C)$-fan를 생각해봐. $V(C)$ 를 $k-1$조각으로 나누고 각 segment 가 $S-\{x\}$의 시작이라고 치자. pigeonhold principle로 인해 두 개의 path 는 $C$의 같은 segment에 걸리게 된다. 이 path로 x를 흡수하면 $S-\{x\}$의 두 vertices를 흡수하는 꼴이 된다.

 

여기에서 가장 길게 나올 수 있는 cycle의 길이는 $n$이다.

 

Definition.

Hamiltonian cycle: spanning cycle. 모든 vertex를 통과하는 cycle

그래프가 Hamiltonian: Hamiltonian cycle을 가짐.

 

일단 $\delta(G) +1$ 만큼의 cycle은 무조건 있고, 그러니까 $\delta(G) = n-1$이면 Hamiltonian cycle을 가진다.

 

Corollary <Dirac's theorem>

$G$가 n-vertex graph고 $n \geq 3$인데다가 $\delta(G) \geq n/2$ $\Rightarrow$ G is hamiltonian

 

Corollary <Ore's theorem>

$G$ 가 n-vertex graph고 $n \geq 3$인데다가 $d(u) + d(v) \geq n$ for all $uv \notin E(G)$ $\Rightarrow$ G is hamiltonian

 

Lemma <Ore's lemma>

$u, v$가 non-adjacent vertices이고 $G$가 n-vertex graph인 상태

$d(u) + d(v) \geq n$ then $G$ 가 hamiltonian $\Leftrightarrow$ $G+uv$ 가 hamiltonian

Hamiltonian 인 상태에서 친구의 합이 $n$명보다 큰 두 어색한 친구를 붙여줘도 hamiltonian 이 유지된다.

$\textit{Proof}$

$G$가 hamiltonian 이면 $G+uv$도 그렇다. 

만약 $G+uv$가 Hamiltonian 인데 $G$는 아니다? 그러면 $uv$ 는 $G+uv$의 spanning cycle에 있기는 하지 일단.

$v_1, ..., v_n$ 이 spanning path 고, $u= v_1$, $v=v_n$이라고 하자. 만약 $u$의 neighbor 가 $v$의 neighbor를 즉시 따라온다면, $uv_{i+1}, vv_i \in E(G)$ 니까, $v_iv_{i+1}$ 을 빼는 건 $G$의 spanning cycle을 준다.

$S = \{i: uv_{i+1} \in E(G)\}$ and $T = \{i: vvI \in E(G)\}$

Then $|S| + |T| = d(u)+ d(v) \geq n$ 이라서

$S, T \subseteq [n-1]$ 이면 $i \in S \cap T$가 있으니 이게 G의 hamiltonian cycle 이다.

 

Definition

<Hamiltonian> closure <$C(G)$>:  degree의 합이 최소 $n$인 non adjacent vertices 들을 붙여주는 edge들을 pair가 안남을 떄까지 반복적으로 추가하면서 만든 closure. 

$G$ is closed: $C(G) = G$ 솔직히 close가 뭔지 잘 모르겠다

 

Theorem <Bondy-Chvatal>

Graph 의 closure 은 <edge의 추가 관계를 신경 안쓰면> unique 하고, 그래프가 Hamliltonian 이다 $\Leftrightarrow$ closure 가 Hamiltonian이다

closure가 hamiltonian 이면, 그건 유일하고, 그래프도 hamiltonian이다

$\textit{Proof}$

Closure $G_1$ 이 $e_1, ..., e_r$을 추가해서 만들었고

Closure $G_2$ 도 $f_1, ..., f_s$ 순서로 만들어졌다고 치자.

edge들이 추가될 떄마다 degree sum 이 최소 $n$은 넘긴다 이거야.

만약에 pair $(u,v)$ 가 합쳐질만 했으면, list가 끝나기 전에 이미 추가되었을 거라고.

$f_i$가 $G_1$에 포함 안 된 첫 edge라고 하자. 그러면 $f_1, ..., f_{i-1} \in E(G_1)$ 이고, $f_i$ 는 $G_1$에 추가될만 했을테니 아마 $G_1$에 있었어야 했을 거야. 이건 모순이라서 $G_2 \subseteq G_1$이라는 거고, $G_1 \subseteq G_2$겠지.

 

Theorem <Chvatal>

$n \geq 3$인 상태에서 $G$의 degree가 $d_1 \leq ... \leq d_n$이라고 하자.

$i<n/2$ 아 $d_i > i$ 또는 $d_{n-i} \geq n-i$ $\Rightarrow$ G는 Hamiltonian

degree sequence 가 degree 적은 순서대로 이쁘게 정렬되어있으면 $G$가 Hamiltonian이다

$\textit{Proof}$

일단 $G$가 closed라고 가정하자.

만약 $G$가 closed 고 $G \neq K_n$이면 Chavtal's condition 은 실패 for some $i < n/2$

왜냐하마녀 $G \neq K_n$이니까 non adjacent 한 $u,v$, 그것도 degree sum이 maximum인 애들로다가 골라봐.

$G$가 closed니까, $uv \notin E(G)$라서 $d(u) + d(v) < n$이라고. 

여기서 $d(u) \leq d(v)$로 $u$가 degree 적은 쪽이고, $d(u) < n/2$가 된다. $i=d(u)$라고 해봐.

$v$의 neighbor가 아닌 애들은 degree가 아무리 많아봤자 $d(u)$야. $d(u) + d(v)$가 최고인 둘을 골랐댔잖아.

그런 애들이 $n-1-d(v)$ 만큼 있다고.

$n-1-d(v) \geq d(u) = i$라서 최소 $i$개의 vertex 들이 degree가 암만 많아봤자 $i$개라는거야.

비슷한 얘기로 $u$의 neighbor가 아닌 애들도 degree가 아무리 많아봤자 $d(v)$개고, 그런 애들이 $n-1-d(u)$만큼 있어. 

아까 $d(u) \leq d(v)$라고 했지? $u$자체가 degree가 암만 많아봤자 $d(v)$야. <??????>

$d(v) < n-d(u) = n-i$ 니까, $n-i$개의 vertex가 degree가 $n-i$개보다 적은 거.

그러니까 $d_i \leq i$ and $d_{n-i} < n-i$ 라서 $i=d(u)$일 때 Chvatal's condition 이 안 먹힌다.