Graph coloring (chromatic number) proof How can i prove this?
If a graph $G$ is countable and if $a \in \mathbb{N}$, then $\chi(G) \leqslant a$ if and only if $\chi(S) \leqslant a$ for every finite subgraph $S$.
 A: This is the de Bruijn-Erdős theorem, and is an example of a compactness argument. We do not need the assumption that $G$ is countable, but it makes the proof more elementary. 
One can argue as follows: (I am leaving some minor details out.) Clearly, if $\chi(G)\le a$, then also $\chi(S)\le a$ for any finite subgraph $S$. 
Conversely, enumerate the vertices of $G$ as $\{v_i\mid i\in\mathbb N\}$. Fix a set $A$ of colors with $|A|=a$. If $a$ is infinite, there is nothing to prove, so assume it is finite. For each $n$, let $C_n$ be the set of colorings of the subgraph of $G$ with vertex set $V_n:=\{v_1,\dots,v_n\}$ using only colors from $A$. Note that $C_n$ is non-empty, as we are assuming $\chi(S)\le a$ for any finite subgraph $S$. Note also that $C_n$ is finite, as a coloring is a function from the set $V_n$ of vertices to $A$, satisfying some conditions, but since $V_n$ and $A$ are finite, there are only finitely many such functions, regardless of whether they satisfy these conditions or not. Finally, note that for any $c\in C_m$, if $m>n$, then the restriction of $c$ to $V_n$ is in $C_n$. 
Now proceed recursively: Since $C_1$ is finite, for some $c_1\in C_1$ there are infinitely many $m$ such that there is a function $c\in C_m$ with $c\upharpoonright V_1=c_1$. Since $C_2$ is finite, it follows that there is some $c_2\in C_2$ such that $c_2\upharpoonright V_1=c_1$ and for infinitely many $m$ there is a $c\in C_m$ with $c\upharpoonright V_2=c_2$.  Since $C_3$ is finite, it follows that there is some $c_3\in C_3$ such that $c_3\upharpoonright V_2=c_2$ and for infinitely many $m$ there is a $c\in C_m$ with $c\upharpoonright V_3=c_3$. Etc.
These functions $c_1,c_2,\dots$ are compatible, in the sense that $c_i$ is just the restriction of $c_j$ to $V_i$ whenever $i<j$. This means that we can "patch them together" to form a function $c$ with domain $\{v_i\mid i\in\mathbb N\}$. The point is that each $c_i$ is a coloring with colors from $A$, and therefore $c$ is too, because otherwise there are vertices $v_i$ and $v_j$ with $i<j$ such that $c(v_i)=c(v_j)$ and $\{v_i,v_j\}$ is an edge of $G$. But by construction, $c(v_j)=c_j(v_j)$ and $c(v_i)=c_i(v_i)=c_j(v_i)$, so $c_j$ is not a coloring of the subgraph of $G$ with vertex set $V_j$, a contradiction.
Arguments of this sort are called compactness arguments because they can be deduced as corollaries of purely topological assertions about the compactness of certain spaces; in this case, the compactness of the countable product of a family of finite (discrete) spaces. The general version of these arguments can be deduced from Tychonoff's compactness theorem, and is sometimes called Rado's selection principle (though Tychonoff's theorem is equivalent to the full axiom of choice, this principle is strictly weaker than it). 
Truszczynski-Tuza and Rav wrote a nice survey of applications of this result: Rado’s Selection Principle: applications to binary relations, graph and hypergraph colorings and partially ordered sets, Discrete Mathematics, 103, (1992), 301–312. MR1171783 (93j:05004). A well-known case where the de Bruijn-Erdős theorem is relevant is the  Hadwiger-Nelson problem on the chromatic number of the plane; note that this is an example where the countable version of the result does not suffice.  
