I have come across a solution using some graph theory for the case when G is countable. For the uncountable case it goes into Zorn's Lemma and advanced set theory.It is quite tough for a math contest for the uncountable case.(I have a solution for both the cases communicated to me by a past medalist.)

No one solved that problem...........(at the test.....)

By the De Bruijn-Erdős theorem, we are done.

@above, i think this is essentially proving a particular case of the De Brujin-Erdos theorem for otherwise it is completely trivialized by the theorem and not an olympiad problem.

anantmudgal09 wrote: @above, i think this is essentially proving a particular case of the De Brujin-Erdos theorem for otherwise it is completely trivialized by the theorem and not an olympiad problem. So what.......we are permitted to use any theorem......so existing in the world.....(with its source...) So I guess.......it's a legal to use that theorem.......

Uh... not exactly. You can use any theorem with its source only if it does not completely trivialize the problem.This is somewhat prevalent and common to Olympiads for some reason or otherwise you dont get points at all.This just the way it is. Of course in discussions and research it is allowed and broadens Mathematical perspectives.

The countable case. Put $k$ instead of $10$. Let $G_0$ be a finite subgraph of $G$. We call a coloring of $G_0$ admissible if it can be extended to a coloring of any finite subgraph of $G$, which contains $G_0$ as a subgraph. Claim 1: There exists an admissible coloring for any finite subgraph of $G$. Proof: Suppose on the contrary $G_0\subset G$ is finite and it doesn't have an admissible coloring. All $k$-colorings of $G_0$ are finite, and for each coloring $c$ of them, there exists a finite subgraph $G(c)$ of $G$ ($G_0 \subset G(c)$), such that $c$ cannot be extended from $G_0$ to a valid coloring of $G(c)$. Now, take the union $U$ of all $G(c)$, which is also finite. It would imply that $U$ couldn't be colored by $k$ colors, a contradiction.$\blacksquare$ Claim 2: Let $G_0$ be a finite subgraph of $G$ and $c$ be some admissible coloring of $G_0$. Denote by $G_0(v)$ the graph obtained by $G_0$ by adding any vertex $v\in G$. Then the coloring $c$ of $G_0$ can be extended to an admissible coloring of $G_0(v)$. Proof: Suppose on the contrary it's not true. Then for any coloring of $v$ by $i$-th color, $i=1,2,\dots,k$, there exists a finite graph $G_i\,,\, G_0\subset G_i \subset G$, such that the coloring of $G_0(v)$ cannot be extended to $G_i$. Take the union $G'$ of all $G_i,i=1,2,\dots,k$. Then the coloring $c$ of $G_0$ can be extended to some valid coloring of $G' $, which brings us to a contradiction. $\blacksquare$ Now enumerate the vertices of $G$ by $v_1,v_2,\dots$ and begin to extend consecutively to admissible coloring of $G(\{v_1,v_2,\dots,v_i\})$ to get a coloring of $G$. The uncountable case. The above idea can be implemented by virtually the same way when the vertices of $G$ are not countable. We just change slightly the definition of admissible coloring. Let $G_0$ is colorable subgraph of $G$, not necessary finite . We call a coloring $c$ of $G_0$ admissible if it can be extended to a coloring of $G_0$ plus any finite additional vertices of $G$. Claim 1 remains true for any finite subgraph of $G_0$. Claim 2 remains valid for any subgraph of $G$. We can assume the vertices of $G$ consist of some segment of ordinals $\{\alpha : \alpha< \beta\}$ for some ordinal $\beta$. We begin to extend some admissible coloring of a single vertex using the transfinite induction. Extending the coloring to a successor ordinal is guaranteed by the Claim 2. Extending to a limit ordinal is just the union of colorings of all of the predecessors.

This could be trivialized using konig's infinity lemma.Consider a graph in which the vertices correspond to coloring of the vertices $\{ v_1,v_2,\dots v_k \}$ for all natural numbers $k$ and draw a directed row from a vertex to the other if and only if the vertex the arrow drawn from has exactly one vertex less than the other coloring and the colors used in the first coloring is exactly repeated in the second coloring.It is clear that there should be some vertex having only $v_1$ as an indicator and having arbitary long directed path starting from that by konig's infinity lemma there should be a infinite directed path starting from that vertex which gives exactly the coloring we needed. Remark:The proof of the konig's infinity lemma isn't much hard in fact if you try to bring the proof of the lemma in the problem you will reach the above post by dgrozev.

This follows by a theroem in propositional logic which says that given a set of formulas $X$ such that every finite subset is satisfiable, then there exists an assignment which satisfies each and every formula in $X$. The proof (which uses Konig's infinity lemma) can be found in these notes, page 12. The proof also can be modifed to give a proof of this problem. (simply branch 10 times instead of 2)