> [!theorem|*] Vizing's Theorem > If a graph $G$ has maximum degree $\Delta(G)$, then $\chi'(G)=\Delta(G)$ or $\Delta(G)+1$. > [!proof] > First note that any vertex has degree at most $\Delta(G)$, so there is at least one color missing from $\{ 1,\dots,\Delta(G)+1 \}$ at that vertex. > > Induction on $e(G)$, where we pick any $xy_{1} \in E(G)$, find a $(\Delta(G)+1)$-coloring $C$ of $G-xy_{1}$. We shall show that $C$ can be modified so that $xy_{1}$ can be colored too. > > Inductively construct the **Kempe chain** of edge-color pairs $(xy_{i}, c_{i})_{i=1}^{k}$ such that $c_{i}$ is missing at $y_{i}$ but present at $y_{i+1}$. For each step, > - Let $c_{i}$ be a color missing from $y_{i}$. If it is already in the chain (say equal to some $c_{j<i}$ present on $xy_{j+1}$), terminate. Otherwise: > - Case 1: If it is also missing from $x$, then we are done -- we can shift the colors downwards by coloring $xy_{i}$ with $c_{i}$, $xy_{i-1}$ with $c_{i-1}$, etc., and finally $xy_{1}$ with $c_{1}$, thereby completing the proper coloring. > - Case 2: otherwise, it is present on some $xy_{i+1}$; append the pair $(xy_{i},c_{i})$ to the chain. > > Since we only have $\Delta(G)+1$ colors, the process must terminate at some length $k \le \Delta(G)+2$, either by case 1 (we are done), or case 2 (there is some $j: c_{k}=c_{j}=:c$). > > For case 2, first check if $c$ is absent at $x$, then we can color $xy_{i}$ with $c_{i}$ for all $i=1,\dots,k$. > Otherwise, shift the colors before $c_{j-1}$ downwards by coloring $xy_{i}$ with $c_{i}$ for $i=1,\dots,j-1$, and leave $xy_{j}$ uncolored. > > Consider the opportunities to recolor: let $c_{0}$ be a color missing at $x$, and note that $c_{0}\ne c_{i}$ for any $i \le k-1$ by choice of $c_{0}$, so its absence is not affected by shifting colors around. > - $[1]$ If $c_{0}$ is missing at $y_{j}$, then color $xy_{j}$ with $c_{0}$ and we are done. > - $[2]$ If $c_{0}$ is missing at $y_{k}$, then shift colors $c_{i}$ ($i=j, \dots, k-1$) downwards by coloring $xy_{i}$ with $c_{i}$. This leaves $xy_{k}$ uncolored, which we replace with $c_{0}$. > > If we have neither, create one of them: consider the subgraph $H:= (V,\{ e \in E(G) ~|~ C(e)=c \text{ or }c' \}),$and note that $\Delta(H) \le 2$, so it has components made up of paths and cycles. In particular $x,y_{j},y_{k}$ all have degree $1$ ($x$ only has $c$, and $y_{j,k}$ only have $c_{0}$), so they are ends of paths. > > Therefore at least one of $y_{j},y_{k}$ doesn't belong to the same component as $x$. Now flip the colors $c,c_{0}$ in the loner's component, and one of $[1,2]$ is then satisfied: $c_{0}$ is still absent at $x$, as $x$ is in another component, unaffected; but now after flipping, $c_{0}$ is no longer present at that flipped vertex. ### Vizing Class 1 and 2 Graphs > [!definition|*] Vizing's Classes > A graph $G$ is **class-1** if $\chi'(G)=\Delta (G)$, and **class-2** if $\chi'(G)=\Delta (G)+1$. A common trick of proving that a graph is class 2 is by showing that $\Delta (G)$ colors is too few: > [!examples] Class-2 graphs > *Complete graphs ($n$ odd)* If $K_{r}$ is the complete graph with $r$ vertices, $r$ odd, then it is class-2: any $(r-1)$-coloring must cover the $r(r-1)$ total degree of the graph, so each color gets an average of $r$ degrees or $r / 2$ edges. Since $r$ odd, there must be a color with at least $\lceil{r / 2}\rceil$ edges. But that covers $r+1$ vertices, a contradiction. > > *$r$-regular graph ($n$ odd)* More generally, if $G_{r}$ is an $r$-regular graph on an odd number of vertices ($r$ even by the handshake lemma), it is class-2. Again a $r$-coloring needs an average of $n / 2$ edges per color, and $n$ odd forces a color to have at least $2 \lceil n / 2 \rceil=n+1$ vertices. Class 1 graphs usually require direct construction/proofs that they are $\Delta$-colorable: > [!examples] > *Bipartite graphs* If $G=A \cup B$ is bipartite, then it is class-1. > - If $G$ is $r$-regular, then Hall's theorem applies, so use it $r$ times to obtain $r$ edge-disjoint matchings, i.e. the $r$ colors. > - Remove the matching obtained after each use of Hall's theorem, and $G$ is $r-k$ regular after $k$ removals. > > > [!proof]- Proof for general bipartites > > - First prove that there is a partial matching from $A$ to $B$ (and vice versa) that covers all vertices of degree $\Delta(G)$. > > - Then any such $A \to B$ matching $M_{1}$ and $B \to A$ matching $M_{2}$ has union $M=M_{1} \cup M_{2}$ where each component has one of $M_{1,2}$ covering all vertices of the component. > > - Therefore there is a matching between $\Delta$-degreed vertices in $A,B$. Now remove them (by coloring them as color $\Delta$) and induct on $\Delta$ to prove the result. >