A graph $G$ with an uncountable set of vertices has a $k$-coloring if and only if every finite induced subgraph has a $k$-coloring. The above theorem with only a countably infinite set of vertices was straightforward with Konig's Lemma. However, what happens if $G$ has uncountably many vertices. Would the theorem still be true? If not, is there a hint to prove this? 
 A: Yes, it's true. It's called the De Bruijn–Erdős theorem. It's an easy consequence of the Tychonoff product theorem, or rather, the special case of Tychonoff's theorem which says that a product of finite spaces is compact.
Let $G=(V,E)$ be a graph, let $k\in\mathbb N,$ and let $X$ be the set of all (not necessarily proper) vertex colorings $f:V\to\{1,\dots,k\}.$ We can think of $X$ as a Cartesian product $X=\prod_{v\in V}X_v$ where $X_v=\{1,\dots,k\}$ for each vertex $v.$ Let $X_v$ have the discrete topology, and let $X$ have the Tychonoff product topology. By Tychonoff's theorem, $X$ is a compact space.
For each edge $e=\{u,v\}\in E,$ let $F_e=\{f\in X:f(u)\ne f(v)\}.$ From the fact that $X_u$ and $X_v$ are discrete spaces it easily follows that $F_e$ is a closed set. The family $\mathcal F=\{F_e:e\in E\}$ will have the finite intersection property if every finite subgraph of $G$ is $k$-colorable. Since $X$ is compact, it follows that the whole family $\mathcal F$ has a nonempty intersection. Any element $f\in\bigcap\mathcal F$ is a proper coloring of $G.$
Alternatively, here's a proof using just Zorn's lemma. Since you just wanted a hint, I will leave the details to you.
Let $k\in\mathbb N$ and let $G=(V,E)$ be a graph such that every finite subgraph of $G$ is $k$-colorable. Let me call $f$ a "partial coloring" if $f:X\to\{1,\dots,k\}$ for some set $X\subseteq V$ and $f$ is a proper coloring of the subgraph of $G$ induced by $X.$ Let me call a partial coloring $f:X\to\{1,\dots,k\}$ "good" if, for every finite set $Y\subseteq V,$ we can extend $f$ to a partial coloring $g:X\cup Y\to\{1,\dots,k\}.$ Let $P$ be the set of all good partial colorings, partially ordered by inclusion.


*

*$P\ne\emptyset$ since $\emptyset\in P$.

*The union of a chain of good partial colorings is a good partial coloring.

*By Zorn's lemma, $P$ has a maximal element.

*If $f$ is a maximal element of $P,$ then $\operatorname{dom}f=V,$ i.e., $f$ is a proper $k$-coloring of $G.$
