# Results in graph theory proved using other areas of math, and vice versa

I'm curious about learning graph theory, as it seems to pop up in some unexpected places. In order to get a partial feel for the subject, I was wondering if anyone could point me to some survey articles which focus on the interplay between graph theory and other areas of math.

Essentially, I'm looking for situations where either a result in graph theory is proved using tools previously thought to be very distant from graph theory, or a result in a field thought to be very distant from graph theory for which a graph theoretic proof exists (e.g., a proof of the Nielsen-Schreier theorem with group actions on trees).

-
Here's a group theory paper I wrote that makes constant use graph theory. It's not a survey, but it focuses specifically on tying group theory and graph theory together, so it sounds like what you're looking for. – Alexander Gruber Jan 21 '14 at 1:56
I don't know whether this would qualify as 'fields thought to be distant from graph theory', but Erdos's probabilistic proofs of the existence of certain Ramsey graphs arguably came from a world thought to be completely unrelated, and revolutionized the theory. – Steven Stadnicki Jan 21 '14 at 6:20
Graph theory offers one way to think about problems in additive combinatorics. For example, Szemeredi's Regularity Lemma can be used to prove Roth's theorem that there is a 3-term arithmetic progression in any subset of the naturals with positive density. I wrote some notes on the topic: link. See Tao's article link on structure and randomness; one way to think about it is with graph theory. – Holden Lee Jan 21 '14 at 22:01
Looks like if you prove that a graph is hamiltonian in a polynomial time you can prove P=NP (a million dollar problem of clay institute). – GarouDan Jan 21 '14 at 23:40