Introduction to Graph Theory

Question

I was wondering what might be a good way to learn graph theory from scratch. I have a basic background in math (calculus, diffeq, linear), and thought that I might be able to pick up Diestel's book as it suggested it as a good "first course" in graph theory, but knew it was over my head on literally the first sentence:

Is there a more friendly introduction to graph theory that assumes no previous knowledge on these notational elements? What might be a good place to start?

Answer 1

With no background in combinatorics, I recommend starting with Discrete Mathematics: Elementary and Beyond by Lovász, Pelikán, and Vesztergombi. This covers basic counting techniques and elementary set theory, but out of 15 chapters total, chapters 7-10 and 12-13 are on topics in graph theory.

After looking at a couple of other books, here are the things that (in my mind) make this one stand out:

1. It has a more informal style. It uses mathematical notation, but does not exclusively rely on it; it mentions mathematical terminology, but only when that simplifies the exposition, not for its own sake.
2. It is example- and problem-driven. For graph theory in particular, it starts each section by an actual word problem (though not always a practical one) that we model by a graph, and then shows how the graph theory problem arises from it. Often, it refers back to these examples in the middle of more detailed explanations to help make them more concrete.

I think that this makes the book easier to read, and modeling things by graphs is a genuinely useful skill that deserves to be taught by lots and lots of examples. The drawback is that there will be a bit more of a learning curve, at first, if you go on to an advanced source like Diestel which is written very formally and concisely.