---
tags: NTNU,CSIE,必修,Discrete Mathematics
title: Graph2
description:
---

# Graph theory
Theorem. Let $G = (V,E)$ be an undirected graph with m edges. Then
$$
2m = \sum_{v\in V} deg(v)
$$

## Bipartite graphs(二分圖)
- A simple graph G is bipartite if its vertex set **V can be partitioned into two sets** V1 and V2 such that every edge in the graph **connects a vertex in $V_1$ and a vertex in $V_2$.**
- 將graph G 分成兩堆$V_1, V_2$，且圖中所有的邊要連接$V_1$ 和 $V_2$。

- The pair $(V_1,V_2)$ is called a bipartition of the vertex set $V$; each of $V_1$ and $V_2$ is called a partite set.

### Matching in Bipartite Graphs
A matching in a simple graph $G = (V,E)$ is a subset of $E$ such that no two distinct edges in the set are incident with the same vertex.

## Hall Marriage Theroem
**Theorem**
The bipartite graph $G = (V,E)$ with bipartition $(V_1,V_2)$ has a complete matching from $V_1$ to $V_2$ if and only if $|N(A)| \geq |A|$ for all subsets $A$ of $V_1$.

**Proof**
- Necessity (the “only if” part): the $|A|$ vertices matched to $A$ must lie in $N(A)$.
- Sufficiency (the “if” part):

---
<!--Not finished-->
- Induction Basis: if $|V_1| = 1$, then we may match the vertex in $V_1$ with any of its neighbors

Case(i): Remove an edge e , alon with its endpoints u and v, and let the resulting bipartite graph be G' with bipartition$(V_1', V_2')$.
- For $A\subseteq V_1', |A| < |N(A)| \leq |N(A) \cap V_2'| + 1.$ Namely, $|A| \leq |N(A)\cap V_2'|$ for all $A \subseteq V_1'$ in $G'$
- By the inductive hypothesis, there is a complete matching from $V_1'$ to $V_2'$ in G.
- Along with e we have a complete matching from $V_1'$ to $V_2'$

Case(ii): (there exists a subset $A\subseteq V_1$ of size at most k such that $|A| = |N(A)|$)
- Consider the bipartite graph induced by $A \cup N(A)$. Since $|A|\leq k$, by inductive hypothesis there is a complete matching $M_1$ from $A$ to $N(A)$.
- process
- For $B \subseteq V_1 - A$, let $N'(B) = N(B)\cap (V_2 - N(A)$.
- We claim that $|B| \leq |N'(B)|$.
- Otherwise $(|B| > |N'(B)|)$ then
$$|B\cup A| = |B| + |A| > |N'(B)| + |N(A)| = |N'(B) \cup N(A)| = |N(A\cup B)|$$
- Since $|B| \leq k$, by the inductive hypothesis there is a complete matching $M_2$ from $V_1-A$ to $V_2-N(A).$
- The matching $M_1\cup M_2$ is a complete matching from $V_1$ to $V_2$.
$$Q.E.D(得證)$$