# 2020-04-10 Fundamental Concept III
[video](https://www.youtube.com/watch?v=cNXxtyS2t_0&list=PL8xY3250v6CSrLIsKMFLyrCfWonR1STtt&index=6&t=0s)
###### tags: `圖論`

## 講義: fundamental_concept_1_2020

## p.23 Recall biconditional method
Direct method $P \Rightarrow Q$
Contrapositive metjod $\sim Q \Rightarrow \sim P$
Contradiction $\sim (P \land \sim Q)$

三個等價敘述

## P.24

* **Theorem** :
An edge is a cut-edge if and only if it belongs to no cycle.

* 補充 cut-edge : an edge whose deletion increases the number of components.

proof:
e=(x, y): an edge
H-e is connected iff e belongs to a cycle

1. $!P \Rightarrow !Q$
H-e is connected 就代表 e 不是cut-edge(!P)

## P.25

2. $!Q \Rightarrow !P$
e 在 cycle裡(!Q)

## P.26

* **Lemma**: Every **closed odd walk** contains an **odd cycle**.

odd walk指的是 edge 是odd
close就是出發點和終點一樣(走回出發點)

Case 2 : 拆成兩半，一邊odd，一邊even

basis到induction的過程要補上假設:長度大於1，小於W的close odd walk，contain 一個 odd cycle ($Strong ~ Induction$)

## P.27
Note:
* disjoint (set和set之間): set之間沒有共同元素
* independent(set裡的element):同一個set中的點沒有連線

## P.28 & Extra
[ref1](https://proofwiki.org/wiki/Graph_is_Bipartite_iff_No_Odd_Cycles)
* **Theorem**:

A graph is bipartite if and only if it has no odd cycle.

$Proof:$
::: info
<font color=#000000>

$\Rightarrow :$
堆和堆之間連線如果要形成cycle，就必須出去再回來，這樣形成的只會是even cycle，就算是沒有cycle也不會是odd cycle

$\Leftarrow :$

* Case 1: G裡沒有cycle

- 把每一個edge的兩端放在不同堆裡

* Case 2: G裡不是odd cycle
- 分兩堆最常用的技巧是長度(odd、even)



>[color=#00a000]
>
>真的猛
>[name=Omnom]

</font>
:::

## P.29 Eulerian

* Def : **closed trail** containing all edges.

+ Trail is a walk with **no repeated edge**
+ $circuit$ : closed trail

## P.30
* **Lemma** :
If every vertex v of a graph G has degree at least 2, then G contains a cycle.


1. u 如果是 endpoint of maximal path $P$，那麼 $u$ 的 neighbor 都會在 $P$ 上。

考慮在u左端新增一個新的vertex x的話，那麼u就不會是endpoint

2. $u$ 的degree至少為2 $\rightarrow$ $u$ 的neighbor $v_1$, $v_2$也在 $P$上 <br/> $v_1$, $v_2$中間至少有2種path：^1^在$P$上、^2^透過$u$

## P.31

* **Theorem**:
A graph G is Eulerian if and only if it has ++**at most** one nontrivial component++ and ++its vertices all have **even degree**++.

Note:
trival component: no edges
(但是1個點的Graph是Eulerian)

* $proof$
:::info
<font color=#000000>

$\Rightarrow$
(1).如果有2個nontrivial component，根本不可能是尤拉圖，因為沒有trail可以連他們兩個
(2).點必須要一進一出，所以degree必須是偶數

$\Leftarrow$
Prove by **Strong Induction** on the number of **edges m**.

**Basis**: m=0 一個點
(Not violate def. of Eulerian graph)

**Induction**: m>0. (In fact, by assumption, m should ≥ 2.)
The nontrivial component has a cycle $C$.
(Recall Lemma: If every vertex $v$ of a graph $G$ has degree at least 2, then $G$ contains a cycle.)

Let $G’=G-E(C)$
將$G$的cycle $C$扣除(每個vertices degree少2)，產生諸多component

By induction hypothesis, each component of G’ has an Eulerian circuit.
Merge these circuits to obtain an Eulerian circuit of G.
(增加2 edges，一進一出)
</font>
:::
## P.33

* **Theorem**:
For a connected nontrivial graph with exactly 2k odd vertices, the minimum number of trails that decompose it is max{k, 1}.

Recall: trail:no repeated edge
G=(V,E)是connected. 有2k個degree為odd的點
$\Rightarrow$ decompose之後，最少trail數為max{k,1}

## P.35 Vertex Degree and Counting

Maximum degree: $\Delta(G) = max_{v \in V(G)}\{d_G(v)\}$
Minimum degree: $\delta(G) = min_{v \in V(G)}\{d_G(v)\}$

Def: **regular graph**
$\Delta(G)$ = $\delta(G)$
$k$-regular: common degree is $k$

## P.36 Vertex Degree and Counting (Conti.)

$Def$:
**order** of a graph : number of vertices or |V(G)|
**size** of a graph :　number of edges or |E(G)|

$Proposition : (Degree-Sum ~Formula)$

$\sum_{v \in V(G)}d(v)=2e(G)$, $\forall$ graph $G$

$Corollary$ 2: 奇數degree的點有偶數個，由proposition可以得知不可能有偶數個($2e(G)$ is even)

## P.37 Vertex Degree and Counting (Conti.)

**Proposition**:
If $k>0$, then a $k$-regular bipartite graph has the same number of vertices in each partite set.

$proof$:
拆成X和Y兩邊，edge分佈於X,Y之間，然後由於是k regular，X堆和Y堆分到的點的個數會一樣

## P.38
**Proposition**:
The minimum number of edges in a connected graph with $n$ vertices is $n-1$. (其實就是tree)

$proof$:
用到n vertices 和 k edges 至少有 n-k component，如果k=n-2，那就會有2個components，那就不會是connected graph

## P.39

## P.40
**Proposition**:

If $G$ is a simple $n$-vertex graph with $\delta(G)≥ \frac{(n-1)}{2}$, then $G$ is connected.
($\delta(G)$是G裡最小的degree)


$proof$:

:::info

<font color=#000000>

$G$ is simple $\Rightarrow$ $| N (u) |≥ δ (G) ≥ \frac{n−1}{2}$ , similarly for $v$
(simple: 一個neighbor 對應一個degree)
N (u)是指neighbor數量 = u 點 degree<br/>
對於 $u ≠ v$, **且$u,v$不相連**, $| N (u) ∪ N (v) |≤ n − 2$ (指的是u和v的common neighbor數會小於等於n-2，u,也就是扣掉u、v這兩點)
($u,v$相連的話會出錯：e.g. $|N (u) ∪ N (v)|=n$)

<br/>

$| N (u) ∩ N (v) |=| N (u) | + | N (v) | − | N (u) ∪ N (v) |$

$≥ \frac{n-1}{2}+\frac{n-1}{2}-(n-2)=1$
($u,v$至少有一個共同neighbor $\Rightarrow$ $u,v$ are connected )
(意思是說即使任兩個不相鄰的點都還是可以透過一個common neighbor來走道另一邊，前提是一開始的假設要先成立)

</font>
:::

## P.41

**Theorem**: Every loopless graph $G$ has a bipartite subgraph with at least $\frac{e(G)}{2}$edges.


關於第3點的說明：
因為H是edge數最多的bipartite graph，所以改變v neighbor的選法時，不應該增加H的edge
$i.e.$ 將 $d_H(v)$拆成兩部分時，當然選最大的啊(murmur)