DMAT_L5

De Bruijn–Erdős theorem: another application of Zorn’s lemma

A graph $G=(V,E)$ is $k-$colorable if it can be colored using $k$ colors such that no two connected vertices have the same color.

Theorem 1(Theorem).

Let $G=(V,E)$ be an infinite graph such that every finite subgraph is k-colorable. This implies $G$ is k-colorable.

Proof

If $G$ is $k$-colorable, there exists a function $\hat{c}:V\to \{1,2,\dots k\}$ such that for all $\{u,v\}\in E$, $\hat{c}(u)\ne \hat{c}(v)$. ${\hat{c}}^{-1}(i)$ is the set of all vertices in $V$ that have color $i$, and there will not exist any edges between its elements.

Define $P\equiv \{G^{\prime }\equiv (V,E^{\prime }):E^{\prime }\supset E,\text{ every finite subgraph of }{G}^{\prime }\text{ is k colorable}\}$. Define a partial order on $P$ by $G_1\le G_2$ if $E(G_1)\subset E(G_2)$. Let $C\subset P$ be a chain. Let $\hat{E}\equiv {\bigcup }_{(V,E^{\prime })\in P}{E}^{\prime }$, and let $\hat{G}\equiv (V,\hat{E})$ be our candidate upper bound for $C$. We have to show that $\hat{G}\in P$, i.e, every subgraph of $\hat{G}$ is k-colorable. Let $H=(U,\tilde{E})$ be a finite subgraph of $\hat{G}$. Let $\tilde{E}=\{e_1,e_2,\dots ,e_n\}$. Let $e_i\in E_i^{\prime },(V,E_i^{\prime })\in C$. Let $E_{i_1}^{\prime }\subset E_{i_2}^{\prime }\subset \cdots \subset E_{i_n}^{\prime }$. $H$ is a subgraph of $(V,E_{i_n}^{\prime })$, which is in $P$, so $H$ is k-colorable.

So, by Zorn’s lemma , the partial order $P$ has a maximal element $\overline{G}=(V,\overline{E})$. Consider the binary relation $x,y\in V$, $x\sim y$ iff $\{x,y\}\notin \overline{E}$. Evidently, $\sim$ is reflexive and symmetric. We will show that it is transitive.

Let $x,y,z\in V$, $x\sim y$, $y\sim z$.
Now, $x\sim y$ $⟹$ $\overline{G}+\{x,y\}\notin P$. So, $\overline{G}+\{x,y\}$ has a finite subgraph $H_1=(U_1,E_1)$ which is not $k$-colorable. Note that $\{x,y\}\subset U_1$ and $\{x,y\}\in E_1$ are forced. Also, for all k-colorings of $H_1\setminus \{x,y\}$, $x$ and $y$ must get the same color.
Similarly, for $\overline{G}+\{y,z\}$ there is a finite subgraph $H_2=(U_2,E_2)$ which is not k-colorable and $\{y,z\}\in U_2$. So, for all k-colorings of $H_2\setminus \{y,z\}$, $y$ and $z$ have the same color.
Now consider $H_1\cup H_2\setminus \{\{x,y\},\{y,z\}\}$. It is k-colorable, and from the properties of $H_1\setminus \{x,y\}$ and $H_2\setminus \{x,y\}$ discussed above, $x$ and $y$ must have the same color, and $y$ and $z$ must have the same color. Thus, $x$ and $z$ must have the same color. So, we have found a subgraph of $\overline{G}$ such that in every possible k-coloring of the subgraph, $x$ and $z$ have the same color. This makes it impossible for $x$ and $z$ to be connected in $\overline{G}$.

So, $\sim$ is an equivalence relation on $V$. It partitions $V$ into equivalence classes.

$$V=\underset{i\in I}{⨆}{V}_i$$

$x\in V_i$ and $y\in V_j$, $i\ne j\in I$ implies $\{x,y\}\in \overline{E}$.

Claim: $|I|\le k$.
Otherwise, pick equivalence classes $V_1,V_2,\dots V_{k+1}$ and $v_i\in V_i$. The graph induced by $\{v_1,v_2,\dots ,v_{k+1}\}$ is a complete graph with $k+1$ vertices, which is not k-colorable.

Thus, $\overline{G}$ is k-colorable. Note that any k-coloring for $\overline{G}$ also works for $G$.