One application of graph theory that's particularly interesting to me
is called Ramsey theory. It's particularly interesting as someone who
debunks a lot of creationist nonsense, because Ramsey theory is in
direct opposition to some of the basic ideas used by bozos to
purportedly refute evolution. What Ramsey theory studies is when some
kind of ordered structure *must* appear, even in a pathologically
chaotic process. Ramsey theory is focused largely on *structures* that
exhibit particular properties, and those structures are usually
represented as graphs.
For example, the most common introductory application of Ramsey theory
is to ask: given a complete graph KN. What is the minimum
N for which you *cannot* assign a 2-coloring to its nodes without
getting a single-colored triangle. The solution is 6: there is no possible assignment of two colors to edges in a complete graph without having at least one single-colored triangle. This is, in fact, known as Ramsey's theorem.
There are a lot of other similar problems, which all have the flavor of looking at progressively larger structures, and asking how large the structure needs to grow before it *must* necessarily contain a particular substructure.
There's the clique theorem, which asks: given a graph with N nodes,
for some number k<N, how many edges can you add before the graph
*must* contain at least one k-clique?
A case where the underlying proof is graph theoretic, but the graph
isn't completely obvious is the Hales-Jewett theorem. This says for any
two numbers N and C, there is a number H such that any assignment of C colors to the cells of an H-dimensional (N×N×N×...×N) cube
*must* contain at least one full row which has the same color. To see how
this reduces to a graph problem, think of each cell of the cube as a vertex,
assigning colors to the vertices, and then looking for a certain kind of
path through nodes assigned the same color.
Hales-Jewett is also sometimes called the tic-tac-toe theorem, because one
way of interpreting it is: H is the minimum dimensionality of a game of
N-in-a-row tic-tac-toe with C players where one player *must* win; the game cannot possibly end in a draw.
The reason why this should be of particular interest in terms of the evolution debates should be obvious: the creationists like to make arguments of the form "X cannot happen, because order cannot arise from chaos". Bzzzt. No, given a large enough disordered system, order *must* inevitably arise in some part of it. What Ramsey theory shows is that disorder, carried to a sufficiently high degree, is a kind of order in itself. In Ramsey proofs, in general, the only way to drag out a process to its Ramsey bound is by *deliberately* being adversarially
chaotic: doing things in a way that specifically delays the order as long as possible. Take K20, and assign a 2-coloring to its edges. Odds are, you're going to get a single-colored triangle long before you've fully colored a subgraph isomorphic to K6; you have to deliberately work to avoid coloring a triangle before you've colored a subgraph of K6.