Reference:
Introductory Combinatorics by Richard A. Brualdi, Chapter 11.
1. Chromatic Number
1.1. $\chi{G}$ and basic properties
$\textbf{Definition}$: The Chromatic Number of a graph $G$, denoted by $\chi(G)$, is the smallest number of colors needed to color the vertices of $G$ so that no two adjacent vertices have the same color.
Let $G$ be a graph with order $n\leq 1$. By definition, it’s easy to see that $1 \leq \chi(G)\leq n$.
$\textbf{Theorem}$: Chromatic number of a graph is bounded by the maximum degree of its vertices.
define
then
Pf. (贪心): Let’s prove this by induction on the number of vertices $n$. pick $x_1$, color it with color 1.
Having colored $x_1,x_2,\cdots,x_k$ with $\Delta+1$ colors, we color $x_{k+1}$ with the smallest color not used by its neighbors. But by definition, $x_{k+1}$ has at most $\Delta$ neighbors, so we can always find a color for $x_{k+1}$.
1.2. Chromatic Polynomial
$\textbf{Definition}$: The chromatic polynomial of a graph $G$, denoted by $P_G(k)$, is the number of ways to color the vertices of $G$ with $k$ colors so that no two adjacent vertices have the same color.
这里称呼它为"多项式"实际上是不严谨的, 后面我们会证明它确实是个多项式.
$\textbf{Theorem}$: If $G$ is a tree, denoted by $T$, then
where $n$ is the order of $T$.
Pf. This is a typical chromatic problem in China’s high school math textbook. Firstly for the first vertice, there are $k$ ways to color it. Then for the second vertice, there are $k-1$ ways to color it. For the third vertice, there are $k-1$ ways to color it. And so on. So the total number of ways to color the tree is $k(k-1)^{n-1}$.
Acturally by “firstly”, “secondly”, I mean that a tree can be spanned by a sequence of vertices, and the first vertice is the root of the tree. Since there is no cycle in a tree, so when you span the tree, you really only need to consider the very former vertice.
$\textbf{Theorem}$: If $G$ is a graph with order $n$, then $P_G(k)$ is a polynomial of degree $n$.
在这里用一些自己定义的符号hhhh.
Pf. We firstly define a binary relation of Graph $\prec$ as the relation that
We then consider two kinds of subgraphs of a given graph $G$. One is the subgraph $G_1$ obtained by deleting an edge $e=\{u, v\}$ from $G$. The other is the subgraph $G_2$ obtained by removing the edge $\{u, v\}$ and merging its adjacent vertices $u$ and $v$.
Suppose we have a $k$-coloring of all the subgraphs of a given graph $G$. Suppose for all the graph $G^\prime\prec G$, we have $P_{G^\prime}$ is a polynomial with the degree $|V(G^\prime)|$, then there are 2 cases,
- $u$ and $v$ are colored with different colors. Then we can color $G$ with the same coloring of $G_1$. so each of the $k$-coloring of $G_1$ is also a $k$-coloring of $G$.
- $u$ and $v$ are colored with the same color. Then this corresponds to a $k$-coloring of $G_2$.
By the above two formulas, we can get that
But by induction, all the subgraphs of $G$ are polynomials with degree of its order respectively. So $P_G(k)$ is a polynomial of degree $n$.
Here we are actually using the [double induction] in Mathematcal Logic. Even though the order(序, 不是阶) we defined is not a well-order, we can still use the double induction to prove the statement.
Actually if we don’t use induction, by simply getting this identity, we can keep deleting edges until we get a tree. But a tree’s chromatic polynomial is a polynomial so the original graph’s chromatic polynomial is also a polynomial (of degree $n$).
1.3. Chromatic Index
$\textbf{Definition}$: Similar to the chromatic number, the Chromatic Index of a graph $G$, denoted by $\chi^\prime(G)$, is the smallest number of colors needed to color the edges of $G$ so that no two adjacent edges have the same color.
Two edges are adjacent if they share a common vertex.
$\textbf{Theorem}$: Chromatic index of a graph is bounded by the maximum degree of its vertices.
The first inequality is trivial as a necessary condition.
But the proof for the second inequality is much more difficult than that of the chromatic number (thus omitted here).
1.4. Five Color Theorem
The [five color theorem] is interesting as it’s firstly thought of as a proof for the four color theorem, but there are some mistakes in the proof so degenerated to this theorem.
$\textbf{Definition}$: A graph is planar if it can be drawn in the plane without any edges crossing.
$\textbf{Example}$: of planar graph
- $K_4$ is a planar graph.
- $K_5$ is not a planar graph.
$\textbf{Theorem}$: Let $G$ be a planar graph, then $\chi(G)\leq 5$.
Pf. of the five color theorem is quite complicated. We shall prove a bunch of lemmas here.
$\textbf{Lemma 1}$: Let $G$ be a simple planar graph of order $n$. Suppose $|E| = e$, $m$ denotes the number of regions in the plane, then
where region means
$\textbf{Lemma 2}$: Let $G$ be a planar graph, then there exists a vertex of degree at most 5.
Pf of Lemma 2. We use the double counting method.