###### tags: `課程筆記`
# 圖形理論
[TOC]
> Introduction to Graph Theory (Second Edition)
> Douglas B. West
## Ch1. Fundamental Concepts
### 1-1 What is graph?
- A loop is 一個邊的 **endpoints 相同**.
- Multiple edges are **很多邊們，有相同 endpoint**
- simple graph 沒有 **loops 跟 multiple edges**
- When u and v are the endpoints of an edge, they are **adjacent**
- complement $\bar G$ of a graph $G$
- **Clique** in a graph: a set of pairwise adjacent vertices 就是全部都彼此相連的最大點點集合個數
- 相反的就是 **Independent set**，不相連的點點配對集合
- A graph G is **bipartite** if V(G) is *the union of two disjoint (possible empty) independent sets* called partite sets of G
- 
- **Chromatic number** of a graph, is the minimum number of colors
- A **path** is a sequence $\{v_1 ,v_2 ,...,v_k\}$ of **distinct vertices**, such that any two consecutive vertices are adjacent
- **cycle** 就是改成頭尾相同 $\{v_0 ,v_1 ,v_2 ,..., v_k ,v_0\}$
- A graph G is **connected** if each pair of vertices in G belongs to a path
- Adjacency matrix and Incidence matrix
- 
- **isomorphism** 表示兩個 graph 之間存在 bijection (一對一且onto) 的關係
- complete graph and complete bipartite
- 
- **self-complementary**：graph is isomorphic to its complement
- A **decomposition** of a graph is a list of subgraphs such that each edge appears in exactly one subgraph in the list，就是分解成不同的小 graph，但每邊只能出現一次
- **Petersen graph**
- 
- If two vertices are nonadjacent in Petersen graph, then they have exactly one common neighbor.
- The Petersen graph has girth 5.(周長為五)
- **automorphism** of G is an isomorphism from G to G
- G: the path with $V(G)=\{1,2,3,4\}$ and $E(G)=\{12, 23, 34\}$. G has two automorphisms: the identity permutation and the permutation $1↔4$ and $2↔3$
- $Kr,s$ has $r!s!$ automorphisms when $r≠s$. $2(r!)^2$ when $r=s$
- A graph G is **vertex-transitive** if for every pair $u,v∈V(G)$, there is an automorphism that maps u to v.
### 1-2 Paths, Cycles, and Trails
- walk is a list of vertices and edges
- A **trail** is a walk with no repeated edge，不能重複邊
- A **circuit** is a closed trail
- 而 path 跟 cycle 不能重複點
- The **length** of a walk, trail, path, or cycle is its *number of edges*. A walk or trail is **closed** if its endpoints are the same
- 
- Every u, v-walk contains a u, v-path.
- A graph G is **connected** if it has a u, v-path whenever $u, v∈V(G)$
- The **components** of a graph G are its maximal connected subgraphs
- Every graph with $n$ vertices and $k$ edges has at least $n-k$ components.
- A **cut-edge or cut-vertex** of a graph is an edge or vertex whose deletion increases the number of components.
- The **induced subgraph** $G[T]$ consists of $T⊆V(G)$ and all edges whose endpoints are contained in T. 就是有選擇的點的邊全都要，比較嚴格
- A graph is bipartite if and only if it has *no odd cycle*.
- 
- An **Eulerian circuit or Eulerian trail** in a graph is a circuit or trail (不能重複邊) containing all the edges
- If every vertex of a graph G has degree at least 2, then G contains a cycle.
- For a connected nontrival graph with exactly $2k$ oddvertices, the **minimum number of trails that decompose** it is $max\{k, 1\}$.
- 一個 trail 能處理全部的 evenvertices＋一組兩個 oddvertex
- 剩下的 oddvertex 兩個兩個一組連起來
### 1-3 Vertex Degree and Counting
- The degree of vertex v in a graph G, or d(v), is the number of **edges incident to v**
- The maximum degree is $∆(G)$,
- The minimum degree is $δ(G)$,
- G is **regular** if $∆(G) = δ(G)$,
- **k-regular** if the common degree is k.
- The **neighborhood** of v, $N_G(v)$ or $N(v)$
- The **order** of a graph G, $n(G)$, is the number of vertices of G
- The **size** of a graph G, $e(G)$, is the number of edges in G
- **Degree-Sum Formula**
- 
- The minimum number of edges in a connected graph with n vertices is n-1
- If G is a simple n-vertex graph with **$δ(G) \geq \frac{(n-1)}{2}$** then G is connected
- 
- The maximum number of edges in an n-vertex **triangle-free** simple graph is $\lfloor \frac{n^2}{4}\rfloor$
- 
- The nonnegative integers $\{d_1, d_2,...,d_n\}$ are the vertex degrees of some graph if and only if $\sum d_i$ is even
- 
### 1-4 Directed Graphs
- A **directed graph or digraph G** is a triple consisting of a vertex set V(G), an edge set E(G), and a function assigning each edge an **ordered** pair of vertices
- An edge is from its tail to its head.
- A **digraph is simple** if each ordered pair is the head and tail of at most one edge
- A **digraph is a path** if it’s a simple digraph whose vertices can be linearly ordered
- The **underlying graph** of a digraph D is the graph G obtained by treating the edges of D as unordered pairs(就是把 digraph 的方向去掉)
- **adjacency matrix A(G) and incidence matrix M(G)**
- An n-vertex path has n **strong components**, but a cycle has only one
- In a digraph G, $\sum_{v∈V(G)}d^+(v)=e(G)=\sum_{v∈V(G)}d^-(v)$
- **Eulerian trail** in a digraph is a trail containing all edges
- **Eulerian circuit** is a closed trail containing all edges
- If G is a digraph with $δ^+(G) \geq 1$, then G contains a cycle，就是 Min out-edge 至少一
- **orientation** of a graph G is a digraph D obtained from G by choosing an orientation (就是選一個方向) for each edge
- **tournament** is an orientation of a complete graph
## Ch2. Trees and Distance
### 2-1 Basic Properties
- A graph with no cycle is **acyclic**
- A **tree** is a connected acyclic graph
- A **leaf** (or pendant vertex) is a vertex of degree 1
- Every tree with **at least two vertices** has at least two leaves.
- **Deleting a leaf** from an n-vertex tree produces a tree with n-1 vertices
- n-vertex graph G, the following are equivalent.
- G is *connected* and *no cycles*.
- G is *connected* and has *n-1 edges*.
- G has *n-1 edges* and *no cycles*.
- G has *no loops* and has, for exactly one *u,v-path*
- Every edge of a tree is a **cut-edge**.
- **Adding one edge** to a tree forms exactly one cycle.
- Every connected graph contains **a spanning tree**.
- If T and T’ are spanning trees of a connected graph G and $𝑒∈𝐸(𝑇)−𝐸(𝑇′)$ ,then there is an edge $𝑒′∈𝐸(𝑇′)−𝐸(𝑇)$ such that $𝑇′+𝑒−𝑒′$ is a spanning tree of G. 就是加別人、扣自己，一樣是樹。
- **distance** from u to v, $d_G(u,v)$, is the $min$ length of a u,v-path.
- **eccentricity** of a vertex $u$, $ε(u)$, is $max_{v∈V(G)}d(u,v)$
- **diameter** of a graph G, diam G, is $max_{u,v∈V(G)}d(u,v)$，也是 $max_{u∈V(G)}ε(u)$
- **radius** of a graph G, rad G, is $min_{u∈V(G)}ε(u)$
- In the graph below, each vertex is labeled with its eccentricity. The radius is 2, the diameter is 4, and the length of the longest path is 7.
> 
- If G is a simple graph, then $𝑑𝑖𝑎𝑚𝐺≥3⇒𝑑𝑖𝑎𝑚\bar{𝐺}≤3.$
- When $𝑑𝑖𝑎𝑚𝐺≥3⇒𝑑𝑖𝑎𝑚\bar{𝐺}≤3.$ there exist nonadjacent vertices $𝑢,𝑣∈𝑉(𝐺)$ with no common neighbor.
- 
- The **center** of a graph G is the subgraph induced by the vertices of minimum eccentricity.
- The center of a tree is a vertex or an edge.
- **Wiener index** of G is $D(G)= \sum_{u,v∈V(G)}d_G(u,v)$，也就是兩兩點 length 的總和
- minimized by stars and maximized by paths
- **star**: A tree has n-1 edges, it has n-1 pairs of vertices at distance 1, and all other pairs have distance at least 2 $\Rightarrow$ star minimizes $D(T)$.
- consider a leaf $x$ in $T$ with its neighbor $v$. If all other vertices have distance 2 from $x$, $x∈N(v) \Rightarrow T$ is a **star**.
$D(K_{1,n-1}) = (n-1) +2{n-1 \choose 2} = (n-1)^2$
- **path**: u is an endpoint of $P_n$
- $D(P_n) = D(P_{n-1}) + C{n \choose 2} \Rightarrow D(P_n) = C{n+1 \choose 3}$
- If H is a subgraph of G,
- then $dG (u, v) \leq dH (u, v)$，有可能最短路徑沒有包含
- and $D(G) \leq D(Pn)$
- so $D(G) \leq D(T) \leq D(Pn)$
### 2-2 Spanning Trees and Enumeration
- **Prüfer code**
- Iteration: At the ith step, delete the least remaining leaf, and let ai be the neighbor of this leaf，刪掉最小葉子，並記下葉子旁邊那個
> 
> 
- 因此若，給 size n 問 tree 可能性，就是**Prüfer code** 的所有可能：Cayley’s Formula [1889]). For a set $S \subseteq N$ of **size n**, there are $n^{n-2}$ trees with vertex set S，就是a數列所有的可能性
- 給所有點的 degree：Given positive integers $\{d1,…,dn\}$ there are $\frac{(n-2)!}{\Pi(d_i-1)!}$，排列數除以可交換數
> 
- Let $\tau(G)$ denote the number of spanning trees of a graph G. If $e \in E(G)$ is not a loop, then $\tau(G)= \tau(G\in e)+\tau(G\notin e)$.
- **Matrix Tree Theorem**
- 
- **graceful labeling**
- 
- If a tree T with m edges has a graceful labeling, then $K_{2m+1}$ has a decomposition into $2m+1$ copies of T.
- 
- A **caterpillar** is a tree in which a simple path (the spine) is incident to (or contain) every edge.就是有一條能到達每一個點的脊椎。
- 
- A tree is a caterpillar if and only if it does not contain the tree Y.
- A **branching or out-tree** is an orientation of a tree having a root of indegree 0 and all other vertices of indegree 1.
- An **in-tree** is an out-tree with edges reversed.
- In a **strong digraph**, every vertex is the root of an out-tree (and an in-tree)
> 
> 
### 2-3 Optimizations and Trees
- **Kruskal**'s Algorithm
>Maintain an acyclic spanning subgraph H, enlarging it by edges with low weight to form a spanning tree. Consider edges in nondecreasing order of weight, breaking ties arbitrarily
- 
- **Dijkstra**'s Algorithm
- 
- **BSF** is an unweighted graph Dijkstra
## Ch3. Matchings and Factors
### 3-1 Matchings and Factors
- **Matching** is a set of non-loop edges with no shared endpoints
- 點 **saturated** by M 就是點在 matching 的邊上
- A **perfect matching** in a graph is a matching that **saturates every vertex**
- A **maximal** matching in a graph is a matching that cannot be enlarged by adding an edge
- A **maximum** matching is a matching of maximum size among all matchings in the graph
- Maximal $\neq$ maximum
- 
- 兩張圖皆為 maximal 但不是 maximum
- **M-alternating path** is a path that *alternates between edges* in M and edges not in M `就是path上的連續邊邊，依序出現是 M 與非 M`
- **M-augmenting path** is an M-alternating path whose 兩端都沒有被 M 碰到
- **symmetric difference**：For two matchings M and M’, $M \Delta M' = (M-M')\cup(M'-M)$
- 
- Every component of the **symmetric difference** of two matchings is a path or an even cycle.
- $F = M \Delta M'$ and $\Delta F \leq2$（就是 Component 每個最大的 degree 為 2）
- every component of $F$ is a path or a cycle
- A matching $M$ in a graph $G$ is a **maximum matching** in $G$ if and only if $G$ has **no M-augmenting path**
- **`Hall's condition`**：An $X$, $Y$-bigraph $G$ has a matching that **saturates $X$** iff $|N(S)| \geq|S|$ for all $S \subseteq X$ `對面鄰居永遠都比我多，那我一定可以被 saturated by a matching`
- 
- 因此 For $k>0$, every k-regular bipartite graph has a *perfect matching*.
- A **vertex cover** of a graph G is a set that contains at least one endpoint of every edge.
- no vertex can cover two edges of a matching, $|matching|\leq|vertex\ cover|$
- 
- If G is a bipartite graph, then the **maximum size of a matching** in G equals **the minimum size of a vertex cover** of G
- The independence number of a graph is the **maximum size of an independent set** of vertices
- 
- Def：
:::success
- maximum size of **independent set $\alpha(G)$**
- maximum size of **matching $\alpha\prime(G)$**
- minimum size of **vertex cover $\beta(G)$**
- minimum size of **edge cover $\beta\prime(G)$**
:::
- Property：
:::info
- In a graph G, $S \subseteq V(G)$ is an **independent set** iff $\bar S$ is a **vertex cover**, and hence $\alpha(G) + \beta(G) = n(G)$
- If G is a graph **without isolated vertices**, then $\alpha\prime(G) + \beta\prime(G) = n(G)$
- If G is a **bipartite graph** with **no isolated vertices**, than $\alpha(G) = \beta\prime(G)$
:::
- In a graph $G$, a set $S \subseteq V(G)$ is a **dominating set** if every vertex not in $S$ has a neighbor in $S$ `我跟我的鄰居全包了`
- The **dominating number** $\gamma(G)$ is the minimum size of a dominating set in G.
- When a graph G has no isolated vertices, every vertex cover is a dominating set, so $\gamma(G) \leq \beta(G)$
- ex：$\gamma(K_n)=1 ；\beta(K_n)=n-1$
### 3-2 Algorithms and Applications
- **Maximum Bipartite Matching**
> 
> 
- [AALG5: Flow networks, maximum bipartite matching example](https://www.youtube.com/watch?v=x2BdRml5lmc)
- Repeated applying the Augmenting Path Algorithm to a bipartite graph produces a **matching and a vertex cover of equal size**.
- **Weighted Bipartite Matching**
- **transversal** of an n-by-n matrix consists of n positions, one in each row and each column
- **Assignment Problem** is finding a transversal with maximum sum
> 
> 
> 
- **The minimum weighted cover** problem is that of finding a cover of minimum cost
- **Stable Matchings**
- 用 greedy 來解即可
> 
> 
### 3-3 Matchings in General Graphs
- Def：
- A **factor** of a graph G is a spanning subgraph of G.
- A **k-factor** is a spanning k-regular subgraph.
- An **odd component** of a graph is a component of odd order.
- The number of odd components of H is **o(H)**.
- A graph G has a **1-factor** iff $o(G-S) \leq |S|$ for every $S \subseteq V(G)$
- 
- 
- 
- 
- Every $3$-regular graph with no cut-edge has a $1$-factor
- 
- Every regular graph of even degree has a $2$-factor
- 
- 
- **f-factors of graphs**
- Given a function $f:V(G) \rightarrow N \cup \{0\}$ an $f$-factor of a graph $G$ is a spanning subgraph $H$ such that $d_H(v) = f(v)$ for all $v \in V(G)$
- 
- A graph $G$ has an f-factor iff the graph $H$ constructed from $G$ and $f$ has a 1-factor
- ***`Edmond’s Blossom Algorithm`***
- [blossom algorithm 影片參考](https://www.youtube.com/watch?v=3roPs1Bvg1Q&t=8s)
> 
## Ch4. Connectivity and Paths
### 4-1 Cuts and Connectivity
- A **separating set** or **vertex cut** of a graph G is a set $S \subseteq V(G)$ such that $G-S$ has more than one component
- The **connectivity** $k(G)$ of $G$ is the minimum size of a vertex set $S$ such that $G-S$ is disconnected or has only one vertex.`就是最少要拿掉 k 點，才能讓圖變 disconnected`
- A graph with more than two vertices has **connectivity 1 iff it is connected and has a cut vertex**
- A graph G is $k-connected$ if its connectivity is at least k
- $k(K_n) = n-1$
- $k(G) \leq n(G) - 2$ when $G$ is not a complete graph
- $k(K_{m,n}) = min\{m, n\}$
- The connectivity of $K_{3,3}$ is $3$; the graph is $1$-connected, $2$-connected, and $3$-connected, but not $4$-connected.
- A graph with more than one vertex has connectivity zero iff it is disconnected. `因為本身就是 disconnected`
- $k(K_1) = 0$
- An n-dimensional hypercube denoted by $Qn$, where the number of vertices are $N = 2n$, and we use an n-bit binary string to denote a node.
- $V(Q2) = \{00,01,10,11\}$
- 
- 
- 
- 
- 
- Let $Q_k$ be a hypercube. Then, $k(Q_k) = k$
- ***`Harary graphs`*** $H_{k,n}$
- 
- 
:::danger
:100: $k(H_{k,n}) = k$ and hence the **minimum number of edges** in a $k$-connected graph on n-vertices is $\lceil \frac{kn}{2} \rceil$
:::
- A **disconnecting set** of edges is a set $F \subseteq E(G)$ such that $G-F$ has more than one component `點是 separating set`
- A graph is **k-edge-connected** if every disconnecting set has at least $k$ edges.
- The **edge-connectivity** $k\prime(G)$ of $G$ is the minimum size of $G$ disconnecting set.
- Given $S,T \subseteq V(G)$ let $[S, T]$ for the set of edges having one endpoint in $S$ and the other in $T$
- An **edge cut** is an edge set of the form $[S, \bar S]$ , where $S$ is a nonempty proper subset of $V(G)$ and $\bar S = V(G) - S$
- 
- Every edge cut is a disconnecting set
- Every minimal disconnecting set of edges is an edge cut
- If $G$ is a simple graph, then $k(G) \leq k\prime(G) \leq \delta(G)$
- 
- If G is a 3-regular graph, then $k(G) = k\prime(G)$
- If $S$ is a set of vertices in a graph $G$, then $|[S,\bar S]| = \sum_{v \in S}d(v) - 2e(G[S])$
- If $G$ is a simple graph and $|[S,\bar S]| < \delta(G)$ for some nonempty proper subset $S$ of $V(G)$, then $|S| > \delta(G)$
> 
- A **bond** is a minimal nonempty edge cut
- If $G$ is a connected graph, then an edge cut $F$ is a bond iff $G-F$ has exactly two components
:::warning
:bulb: *disconnecting set -> edge cut -> bond*
:::
- A **block** of a graph $G$ is a **maximal connected subgraph** of $G$ that has **no cut-vertex**
- If $G$ itself is connected and has no cut-vertex, then $G$ is a block `一個點不足以拆散我們`
- 
### 4-2 k-connected Graphs
- **Two paths** from $u$ to $v$ are **internally disjoint** if they have no common internal vertex
- A graph $G$ having at least **three vertices is 2-connected** iff for each pair $u, v \in V(G)$ there exist internally disjoint $u,v$-path in $G$.
- If $G$ is a $k$-connected graph, and $G’$ is obtained from $G$ by **adding a new vertex $y$ with at least $k$ neighbors** in $G$, then $G’$ is $k$-connected
- $G\prime =$ 
- For a graph $G$ with **at least three vertices**, the following conditions are **equivalent**.
- $G$ is connected and has no cut-vertex.
- For all $x, y \in V(G)$ there are internally disjoint $x,y$-paths.
- For all $x, y \in V(G)$ there is a cycle through $x$ and $y$.
- $\delta(G) \geq 1$ and every pair of edges in $G$ lies on a common cycle.
- In a graph $G$, **subdivision** of an edge $uv$ is the operation of replacing $uv$ with a path $u, w, v$ through a new vertex $w$
- 
- An **ear** of a graph $G$ is a maximal path whose internal vertices have degree 2 in $G$. `不是只有 degree 2 是有 degree 2`
- An ear decomposition of G is a decomposition $P_0, P_1, ...,P_k$ such that $P_0$ is a cycle and $P_i$ for $i \geq 1$ is an ear of $P_0 \cup P_1 \cup ... \cup P_k$
- 
- A graph is $2$-connected iff it has an ear decomposition.
- Furthermore, every cycle in a $2$-connected graph is the initial cycle in some ear decomposition.
- 
- A graph is **2-edge-connected** iff it has a **closed-ear decomposition**, and every cycle in a 2-edge-connected graph is the initial cycle in some decomposition
- A graph has a **strong orientation** iff it is 2-edge-connected
- 
- (Menger 1927). If $x,y$ are vertices of a graph $G$ and $xy \notin E(G)$, then the **minimum size of an $x,y$-cut (separating set)** equals the maximum number of **pairwise internally disjoint $x,y$-paths $\lambda(x, y)$**
> 
> 上左圖：$\{b,c,z,d\}$ is an $x,y$-cut, $\kappa(x, y) = \lambda(x, y) = 4$
> 上右圖：$\{b,c,x\}$ is an $w,z$-cut, $\kappa(w, z) = \lambda(w, z) = 4$
- 
- Substituting “digraph” for “graph” yields the definition of line digraph.
> 
- If $x$ and $y$ are distinct vertices of a graph or digraph $G$, then the minimum size of an $x,y$-disconnecting set of edges equals the maximum number of pairwise edge-disjoint $x,y$-paths `就是上面的邊的版本`
- **Deletion of an edge** reduces connectivity by at most 1.
- A graph is $k$-connected iff it has at least $k+1$ vertices and, for every choice of **x, U with $|U| \geq k$ it has an x, U-fan** of size k
- Suppose G satisfies the fan condition. For $v\in V(G)$ and $U = V(G)-\{v\}$ there is a $v,U$-fan of size $k$
### 4-3 Newtworks Flow Problems
- 
- 
- 
- 
- 
> 
- [補充影片：Ford-Fulkerson in 5 minutes](https://www.youtube.com/watch?v=Tl90tNtKvxs)
- *`Max-flow Min-cut Theorem`*：In every network, the maximum value of a feasible flow equals the minimum capacity of a source/sink cut.
> 
## Ch5. Coloring of Graphs
### 5-1 Vertex Coloring and Upper Bounds
- A **k-coloring** of a graph G is a labeling $f: V(G)\rightarrow S$ where $|S|=k$ (often we use $S=[k]$), and the labels are colors.
- A k-coloring is **proper** if adjacent vertices have different labels.
- A graph is **k-colorable** if it has a proper k-coloring.
- The **chromatic number $\chi(G)$** is the least k such that G is k-colorable.
> 
The chromatic number of the Petersen graph is 3
- A graph G is **k-chromatic** if $\chi(G)=k$
- If $\chi(H) < \chi(G) = k$ for every proper subgraph H of G, then G is **color-critical or k-critical**
- $K_2$ is the only 2-critical graph.
- $K_1$ is the only 1-critical graph.
- The 3-critical graphs are the odd cycles.
- If $H$ is a k-critical graph, then $\delta(H) \geq k-1$
- The **clique number** $\omega(G)$ of a graph G, is the maximum size of a set of pairwise adjacent vertices (clique) in G. `就是全部都彼此相連的最大點點集合個數`
- 
- 
- $\chi(G\times H)=max\{\chi(G), \chi(H)\}$
- [**Greedy coloring**](https://www.youtube.com/watch?v=vGjsi8NIpSE) relative to a vertex ordering $v_1,...,v_n$ of $V(G)$ is obtained by coloring vertices in the order $v_1,...,v_n$, assigning to $v_i$ the smallest-indexed color not already used on its lower-indexed neighbors.
>- $\chi(G) \leq \Delta(G) + 1$，加1表示加上自己點的顏色
>- 
- An **interval representation** of a graph is a family of intervals assigned to the vertices so that *vertices are adjacent iff the corresponding intervals intersect*
> 
> If $G$ is an interval graph, then $\chi(G) = \omega(G)$，$\omega(G)$
> :::info
> 就是全部都彼此相連的最大點點集合個數；圖形上就是最多重疊點的數量
> :::
- If $H$ is a k-critical graph, then $\delta(H) \geq k-1$
> 
- If $D$ is an orientation of $G$ with longest path length $l(D)$, then $\chi(G) \leq 1 +l(D)$. Furthermore, equality holds for some orientation of $G$.
> 
- Brook's Theorem：If $G$ is a connected graph other than a complete graph or an odd cycle, then $\chi(G) \leq \Delta(G)$
### 5-2 Structure of k-chromatic Graphs
- ***`Mycielski’s construction`***
1. Beginning with $G$ having vertex set $\{v_1,v_2,…,v_n\}$, add vertices $U=\{u_1,u_2,…,u_n\}$ and One more vertex $w$
2. Add edges to make $u_i$ adjacent to all of $N_G(v_i)$, and finally let $N(w) = U$
> 
- From a $k$-chromatic triangle-free graph $G$, Mycielski’s construction produces a $k+1$-chromatic triangle-free graph $G’$.
- Every $k$-chromatic graph with $n$ vertices has at least $C(k, 2)$ edges. Equality holds for a complete graph plus isolated vertices.
- :::success
每種兩兩顏色組合最少都會有一個邊
:::
- A ***`complete multipartite`*** graph is a simple graph $G$ whose vertices can be partitioned into sets so that $u \leftrightarrow v$ iff $u$ and $v$ belong to different sets of the partition.
- Every component of $\bar G$ is a complete graph
- A complete $k$-partite graph is $k$-chromatic
- :::info
一個 partite set 就用一種顏色
:::
- When $k \geq 2, K_{n_1, n_2,...,n_k}$ is used to denote the complete $k$-partite graph with partite sets of sizes $n_1, n_2,...,n_k$ and complement $K_{n_1} + K_{n_2} +...+ K_{n_k}$
- 
- Among simple $r$-partite graphs with $n$ vertices, the *Turán* graph is the unique graph with the most edges
- Among the $n$-vertex simple graphs with no $r+1$-clique, $Tn,r$ has the maximum number of edges
- A graph G with no isolated vertices is **color-critical** iff $\chi(G-e) < \chi(G)$ for every $e \in E(G)$
- Proposition. Let G be a $k$-critical graph.
- For $v \in V(G)$ there is a proper $k$-coloring of $G$ in which the color on $v$ appears nowhere else, and the other colors must be appear on $N(v)$.
- For $e \in E(G)$ every proper $k-1$-coloring of $G-e$ gives the same color to the two endpoints of $e$
- Let $G$ be a graph with $\chi(G) > k$ and let $X$, $Y$ be a partition of $V(G)$. If $G[X]$ and $G[Y]$ are $k$-colorable, then the edge cut $[X,Y]$ has at least $k$ edges
- :::warning
至少把兩邊相同顏色的 k 個串聯起來
:::
- Every k-critical graph is k-1-edge-connected`(every disconnecting set has at least k-1 edges)`

### 5-3 Enumerative Aspects
- Given $k\in N$ and a graph $G$, the value $\chi(G;k)$ is the number of proper colorings $f:V(G) \rightarrow [k]$ The set of available colors is $[k]=\{1, 2,...,k\}$; the $k$ colors need not all be used in a coloring $f$. Changing the names of the colors that are used produces a different coloring.
- 
- If T is a tree with $n$ vertices, then $\chi(T:k) = k(k-1)^{n-1}$
- 
- 第一個是 root 有 k 個選擇，其他點都 k-1 個選擇
- 
- *Chromatic recurrence*：If $G$ is a simple graph and $e \in E(G)$, then $\chi(G;k) = \chi(G-e;k) - \chi(G\cdot e;k)$
- 
> eg. $\chi(C_4;k) = \chi(P_4;k) - \chi(K_3;k) = k(k-1)(k^2-3k+3)$
> 
- The chromatic polynomail $\chi(G;k)$ has degree $n(G)$, with integer coefficients alternating in sign and beginning $1,-e(G),…$*`prove by induction`*
- A vertex of $G$ is **simplicial** if its neighborhood in $G$ induces a clique
- A **simplicial elimination ordering** (perfect elimination orderings) is an ordering $v_n,...,v_1$ for deletion of vertices so that each vertex $v_i$ is a simplicial vertex of the remaining graph induced by $\{v_1, v_2,...,v_i\}$ `從 1 2 依序降到 n`
- **Chromatic polynomial** is $k(k-1)(k-1)(k-2)(k-3)(k-2)$ `就是每一點在 elimination 之後能夠塗的顏色`
> 
- A **chord** of a cycle $C$ is an edge not in $C$ whose endpoints lie in $C$.
- A *chordless cycle* in $G$ is a cycle of length at least 4 in $G$ that has no chord.
- A graph $G$ is **chordal** if it is simple and has *no chordless cycle*
:::info
🔼 圖形就會由很多三角形組成
:::
- For every vertex $x$ in a chordal graph $G$, there is a simplical vertex of $G$ farthest from $x$
- A simple graph has a simplicial elimination ordering iff it’s a chordal graph
- A graph is **perfect** if $\chi(H) = \omega(H)$ `(clique number)` for every induced subgraph $H \subseteq G$
- Clique cover number $\theta(G)$ of a graph $G$ is the minimum number of cliques in $G$ needed to cover $V(G)$
- $\theta(G) = \chi(\bar G)$ `猶如 complete multipartite`
- A family of graphs $G$ is **hereditary** if every induced subgraph of a graph in $G$ is also a graph in $G$
- Chordal graphs are perfect.
- A **transitive orientation** of a graph $G$ is an orientation $D$ such that whenever $xy$ and $yz$ are edges in $D$, also there is an edge $xz$ in $G$ that is oriented from $x$ to $z$ in $D$.
- A simple graph $G$ is **comparability** graph if it has a transitive orientation.
- Comparability graphs are perfcet