[Graph Theory] Connections

Definition

walk: sequence $v_1v_2...v_k$  of vertices and a sequence of edges $v_iv_{i+1} \in E(G)$. edge 로 건너건너

Closed walk: $v_1 =v+k$. 어찌되었건 건너건너 돌아옴

trail: all edges are distinct. Edge 안겹치고 건너건너

closed trail: Edge 안겹치고 건너건너 돌아옴

path: all vertices are distinct. Vertex 안겹치고 건너건너

Cycle: closed walk 인데 vertex 안겹치고 건너건너 돌아옴.

Length of the walk: k-1

 

G is connected: all pairs $u, v \in V(G)$, there is a path in G. vertex 안겹치고 어디로든 갈 수 있음

component of G: connected subgraph maximal: G의 일부인데 vertex 안겹치고 어디든 갈 수 있는 뭉치로 최대 사이즈. 뭉치뭉치.

 

disjoint union of G, H: $(V \sqcup V', E \sqcup E')$, V 와 V' 이 disjoint sets.

 

Proposition.

Every walk from u to v contains a path from u to v.

walk 가 있으면 vertex 안겹치고도 갈 수 있다.

$\textit{Proof}$

shortest u,v-walk $W = v_1 ... v_k$ 를 생각했을 떄, 에서 만약 $v_i = v_j$ 이고 $i < j \in [k]$ 라면, $v_1...v_{i-1}v_iv_{j+1}...v_k$ 로 더 짧은 u,v-walk 생겨서 모순. 그래서 $v_1 ... v_k$는 다 distinct 고, 그게 desired path.

 

Lemma

Every odd closed walk contains the edges of an odd cycle

홀수길이 closed walk 는 vertex 안겹치는 홀수개 cycle 의 edge 를 가진다.

odd closed walk $W$가 있다고 쳤을 떄, $W'$ 을 $W$ 안에 더 작은 odd closed walk 라고 치고, 그럼 걔로 인해서 나눠지는 walk 가 even 하나랑 odd 하나가 생겨서 모순 생김.

 

Theorem (Konig Theorem)

A graph is bipartite if and only if it has no odd cycles

odd cycle 이 없으면, 없어야 bipartite graph 다.

bipartite 이면, 좌우 왔다갔다 하고 돌아와야 하니까 cycle 은 모두 길이가 짝수

Odd cycle 이 없다면, 어떤 컴포넌트 안의 $u$ 를 생각하자. 일단 컴포넌트니까 거기 있는 $v$ 들은 죄다 walk가 있고, 홀수개를 거치면 odd 를 label, 짝수 거리면 even 으로 label 을 하고. labelling이 끝나고 v가 둘다 label 되어있을 수는 없다 ($\because$ there is no odd cycle).  홀수랑 짝수로 나뉜 라벨들을 나누면 그게 bipartite.

 

Proposition.

$\delta(G) = \delta \geq 2$ 인 그래프는 length $\delta$ 보다 긴 path 와, $\delta +1$ 보다 긴 cycle 을 가진다.

$\textit{Proof}$

가장 긴 path $v_1 ... v_k$ 를 생각했을 때, 여기$v_1$ 에서 $v_{k-1}$ 사이에 $v_k$ 의 친구들은 다 들어있어야 한다. 아니면 모순. 그래서 $k-1 \geq \delta$ 이니까 $k \geq \delta+1$.

그리고 저 중에 $v_iv_k \in E(G)$, $v_k$ 친구 중에서 가장 먼저 등장하는 $v_i$ 한 명 잡으면 $v_{i+1}$ 에서 $v_k$ 사이에 친구가 또 있어야 한다. 그러면 $k-1 \geq \delta$. $v_i ... v_kv_i$ 가 $k-i+1 \geq \delta+1$ 인 사이클이다.

 

Definition

cut-vertex or cut-edge: vertex 나 edge 를 지우면 그 subgraph 가 G보다 많은 component 를 만든다: component 가 떨어져 나온다.

 

Proposition

$G-e$ 가 connected 이다 $\Leftrightarrow$ e 는 G의 cycle 에 포함된다.

cycle 은 edge 하나 잘라도 connected다. 하나 잘라도 connected 라면 cycle이다.

$\textit{Proof}$

$e = xy \in E(G)$ 인 상황. $G-e$가 connected 라면, x에서 y가는 path가 있다는 뜻. e만 더하면 cycle이 나온다.

e가 cycle C에 있다고 치자. G가 connected 라면 $u, v \in V(G)$ 에서 u-v path P가 있을 거다.

e가 이 P에 없었다면, P 는 G-e 안에 있으니 u-(e)-v 가 있다는 뜻.  그러니까 G-e 는 connected.

 

Proposition

n개 vertex 와 m 의 edge 는 최소 n-m components 를 가진다.

connected n-vertex graph 는 최소 n-1개 edge를 가진다.

$\textit{Proof}$

vertex 하나에 edge 하나 추가당 vertex 하나 추가.

 

Definition

Tree: connected acyclic graph. 싹 연결되어있고 사이클 없음

Spanning tree: spanning subgraph that is a tree: spanning subgraph 만들었는데 tree

leaf: degree 1

isolated vertex: degree 0

 

Propositions

1. Every nontrivial tree has at least two leaves

2. Deletion of a leaf from a tree yields a tree with one less vertex

3. Every n-vertex tree has n-1 edges.

 

Proposition

G 가 n-vertex graph with n-1 edge 일 때 G 가 connected $\Leftrightarrow$ G is acyclic

tree이다.

$\textit{Proof}$

G 가 acyclic 이라면, 모든 컴포넌트가 tree다. 어떤 components 가 $n_1, ..., n_k$ 의 order라면 $n-1 = \sum_{i \in [k]} (n_i -1) = n-k$ 니까, $k=1$이다.

G가 connected라면, n-vertex graph 에 n-2개 edge 만 가져도 disconnected 니까, 모든 edge 가 cut-edge. 그래서 cycle에 포함되는 edge가 없음. acyclic임.

 

Theorem.

모든 connected graph contains a spanning tree.

모든 connected graph 는 spanning tree 를 가진다.

$\textit{Proof}$

cycle에서 edge 를 반복적으로 뺴다보면 acyclic spanning subgraph 를 얻을 수 있다