A ***coin graph*** is a graph that can be represented by a set of disjoint, except possibly touching, *unit* disks in the plane (i.e. the disks are the vertices and the edges correspond to the pairs that touch each other). It's easy to show by induction that $\chi(G)\leq4$ for every coin graph $G$, as there's always a vertex of degree at most 3. 


My question is: what is the smallest order (i.e. the number of vertices) of a 4-chromatic coin graph? 


In this paper by Erdos <http://www.renyi.hu/~p_erdos/1987-27.pdf> there is a coin graph of order 19 that is 4-chromatic (see Figure 1) by I doubt it's the smallest one (it was constructed for a different purpose, having to do with the independence number). The question I asked was proposed for an IMO competition in 1979, see p. 138 question 73 in Djukic, Jankovic, Matic, Petrovic: the IMO Compendium (there is no solution there, however). 


Clearly, coin graphs are also *unit distance graphs*, for the definition see <http://en.wikipedia.org/wiki/Unit_distance_graph>. The smallest 4-chromatic unit-distance graph is probably the Moser spindle <http://en.wikipedia.org/wiki/Moser_spindle> that has 7 vertices.
There is a similar notion of ***matchstick graphs***: those are unit distance graphs drawn in the plane with non-crossing straight-line segments, see <http://en.wikipedia.org/wiki/Matchstick_graph> Note that the Moser spindle is NOT a matchstick graph, although it's planar and unit-distance. 


The second (related) question is: what is the smallest order of a 4-chromatic matchstick graph?


I think the answer (to the second question) is 8. 



Small 4-chromatic coin graphs
Flo's example with 11 is best possible. Let $G$ be a minimal coin-graph which chromatic number four. Then $G$ does not have a cut vertex, nor a vertex of degree at most two. Moreover, there does not exist a separation $(A, B)$ of $G$ of order two with $G[A \cap B]$ an edge (as opposed to a pair of non-adjacent vertices). Otherwise we could 3-color $G[A]$ and $G[B]$ and glue the colorings together to get a coloring of $G$.


Since $G$ is 2-connected, every face is bounded by a cycle. Consider the cycle $C$ bounding the infinite face. The cycle $C$ must be induced, as otherwise there is a 2-separation whose cut set is an edge. $G$ has no vertex of degree two, so every vertex of $C$ has a neighbor in $V(G) - V(C)$ (and specifically, there is at least one such vertex). 


If there is exactly one vertex in $V(G) - V(C)$, then it is adjacent every vertex of $C$ and $G$ is a wheel on 7 vertices which is 3-colorable. Thus, there exist at least two vertices in $V(G) - V(C)$. However, then $|V(C)| \ge 8$. If $|V(G)| \le 10$, then $|V(C)| = 8$, and there are exactly two vertices in $V(G) - V(C)$. It follows that the graph $G$ must be equal to an 8-cycle $C$ with vertices $v\_1, \dots, v\_8$ and two additional vertices $x, y$, each adjacent to a subset of the vertices $\{v\_1, \dots, v\_8\}$. 


For each of the vertices $x$ and $y$, their neighbors must form a subpath of $C$, say $P\_x$ and $P\_y$. The paths $P\_x$ and $P\_y$ can intersect only at their endpoints. Given that $G$ is a coin graph, $|V(P\_x)| \le 5$ and $|V(P\_y)| \le 5$, and we see now that there are two possible cases: either $|V(P\_x)| = |V(P\_y)| = 5$ and $P\_x$ and $P\_y$ have both endpoints in common, or alternatively, $|V(P\_x)| = |V(P\_y)| = 4$ and $P\_x$ and $P\_y$ are disjoint. In either case, the resulting graph is 3-colorable, a contradiction.


