Coloring infinite graphs and the Boolean prime ideal theorem

It is shown that the following theorem holds in set theory without AC: There is a functionG which assigns to each Boolean algebraB a graphG(B) such that (1) ifG(B) is 3-colorable then there is a prime ideal inB and (2) every finite subgraph ofG(B) is 3-colorable. The proof uses a combinatorial lemma on finite graphs.