Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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).

Thanks in advance!

share|cite|improve this question
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
up vote 0 down vote accepted

One of my favorite "unexpected" graph theory results it's Lovász's proof of the Kneser conjecture using topological methods, particularly the Borsuk-Ulam theorem. The proof is beautiful and interesting, maybe the nicest version is the one appearing in the Proofs from THE BOOK book. There is also a great article describing the proof here.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.