Thm(Wilf,1967) Let G be a graph. Then $\chi(G)\leq\lambda_1(G)+1$, where $\chi(G)$ is the chromatic number
A proper vertex coloring is a map $c:V(G)\to\mathbb{N}$ s.t. $c(v_i)\not=c(v_j)$ if $v_iv_j\in E(G)$.
A graph is a k-colorable if there exists a proper vertex coloring
The chromatic number of a graph is the smallest integer k s.t. G is k-colorable, denoted by $\chi(G)$.
(Four color Theorem) Every planar graph is 4-colorable
Lemma Let G be a graph. Then
where $p=\max{\delta(H)|\text{H is an induced subgraph of G}}$, $\delta(G)$ is minimum degree of H.
Proof of Lemma
Use greedy algorithm:
Consider that $c:V(G)\to\mathbb{N}$ such that color the first vertex by the smallest value and color the k-th vertex by using the smallest value that has not been used to color any of the first k-1 vertices that are adjacent to the k-th vertex. So it suffices to show that there is an ordering of the vertices of G for which the greedy algorithm gives an (1+p)-coloring of G.
Let $x_n$ be a vertex of $G=H_n$ having degree at most p.（$x_n$ could be the vertex of G with the degree $\delta(G)$
By the definition of the value of p, the subgraph $H{n-1}=G-x_n$ has a vertex $x{n-1}$ of degree at most p. Continue this process, let $H{n-1}=G-{x_n,x{n-1},\cdots,x{n-i+1}}$ which again has a vertex of degree at most p, denoted by $x{n-i}$ for $i\in[n]$
Then $H{1}=G-{x_n,x{n-1},\cdots,x_{2}}$ is an isolated vertex of degree 0.
Then the ordering $x_1,x_2,\cdots,x_n$ is a desired one.
Proof of Wilf’s Theorem
Let G be a graph. For any induced subgraph H of G, $\delta(G)\leq d(G)\leq\lambda_1(H)\leq\lambda_1(G)$
Therefore, $p=\max{\delta(H)|\text{H is an induced subgraph of G}}\leq\lambda_1(G)$
It follows from the above Lemma
If G is k-colorable, let $c:V(G)\to[k]$ be a k-colorable. $c^{-1}(i)$, the preimage of color i, is an independent set. Independent number of G: $\alpha(G)\geq\max\left{|c^{-1}(i)|\big|i\in[k]\right}\geq n/k$.
So $\alpha(G)\geq n/\chi(G)\geq n/(1+\lambda_1(G))$.
Coloring, Integer flow
Let G be a graph. An integer flow of G is an ordered pair $(D,f)$ where $D$ is an orientation of $G$ and $f$ is an integer function $f:E(G)\to\mathbb{Z}$ s.t. for every vertex v of G $\sum{e\in E^{+}(v)}f(e)=\sum{e\in E^{-}(v)}f(e)$ where $E^{+}(v)$ is the set of all arcs with $v$ as tail and $E^{-}(v)$ is the set of all arcs with v as head.
Recall: this incidence matrix of D is matrix is $\vec{B}$ and $\vec{f}=An integer flow $(D,f)$ is nowhere-zero if $f(e)\not=0$ for all edges of $G$ i.e. $\vec{f}$ has no zero component.
An integer flow $(D,f)$ is a k-flow if $|f(e)|
If G has a k-flow, the orientation in the k-flow does not matter.
Proposition Every Eulerian graph has nowhere 2-flow. A connected graph with a nowhere-zero 2-flow is Eulerian.
Lemma Let $(D,f)$ be a flow of G, then for each $X\subset V(G)$, it holds that
Proof
Since $(D,f)$ is a flow, it follows that, for every vertex v,
So $\sum{e\in E^{+}(v)}f(e)-\sum{e\in E^{-}(v)}f(e)=0$
Note that
Corollary A graph has a nowhere-zero integer flow $\Leftrightarrow$ it has no cut-edge.
Proof
$\Rightarrow$ It follows directly from the above lemma.
$\Leftarrow$ Assume that G has no cut-edge. Then every edge of G belongs to a cycle.
Let $C={C_1,C_2,\cdots,C_k}$ be a set of cycles covering all edges of G.
Every $C_1$ has nowhere-zero 2-flow $(D,f_1)$
Then $(D,f)$ is a nowhere-zero integer flow.
The Coloring-Flow Duality Theorem (Tutte)
Let G be a 2-connected planar graph. Then G is proper face k-colorable if and only if G has a nowhere-zero k-flow. In other words, let $G^{\star}$ be its planar dual. Then $G^{\star}$ is proper k-colorable $\Leftrightarrow$ G has a nowhere-zero k-flow.