Model Theory Vs. Graph Theory
Here's the dirt on how these objects relate to one another:
One interesting and elementary connection between model theory and graph theory is the proof of the four color mapping theorem in the case of infinite graphs. Assuming the theorem in the finite case, the infinite case is a simple matter of applying the compactness theorem of model theory.