6
$\begingroup$

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:

enter image description here

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?

$\endgroup$
12
  • 2
    $\begingroup$ ."no previous knowledge on these notational elements" ... perhaps you could concentrate on learning these notations before starting with the book. $\endgroup$
    – Surb
    Commented Jan 30, 2020 at 21:01
  • $\begingroup$ @Surb -- sure, where then? $\endgroup$
    – David542
    Commented Jan 30, 2020 at 21:01
  • 3
    $\begingroup$ It would benefit you to take a "discrete math" course which covers basics like logic, set theory, etc. That should prepare you better for this. $\endgroup$
    – Alex R.
    Commented Jan 30, 2020 at 21:06
  • $\begingroup$ @AlexR. -- thanks, do you have any recommended books for that as a good 'first course'? $\endgroup$
    – David542
    Commented Jan 30, 2020 at 21:14
  • 1
    $\begingroup$ Diestel's book is a graduate text. You'd probably be better off with an undergraduate text. $\endgroup$
    – saulspatz
    Commented Jan 30, 2020 at 21:14

1 Answer 1

Reset to default
3
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ thanks. How would that compare to something like the link provided above: discrete.openmathbooks.org/pdfs/dmoi-tablet.pdf -- are they interchangeable? $\endgroup$
    – David542
    Commented Jan 30, 2020 at 22:39
  • 1
    $\begingroup$ Well, I am only familiar with the one I suggested - I was a TA several times for a class that used it for students that share your background, which is why I recommended it. It looks like they cover about the same topics in about the same detail. I notice that the Lovász et al. textbook is more example-driven: it gives some problems, and shows how to model them with graphs and then solve. The Levin textbook is a bit more dry and technical (for example, in how it introduces the bipartite matching problem). The upside of the Levin textbook is being free online. $\endgroup$
    – Misha Lavrov
    Commented Jan 30, 2020 at 23:02
  • $\begingroup$ thanks for the feedback. One additional question: what about this one here? ocw.mit.edu/courses/electrical-engineering-and-computer-science/… Does that seem like it covers around the same ground as your suggested book? Since it has video lectures I was thinking of following along with both the pdf and the lectures. $\endgroup$
    – David542
    Commented Jan 30, 2020 at 23:05
  • $\begingroup$ Their graph theory content (at least the text, not the lectures, who knows about the lectures) is here. It covers a lot of the same material, but seems (unsurprisingly) more algorithm-focused, which might or might not be what you want. The lectures might change that balance, though. $\endgroup$
    – Misha Lavrov
    Commented Jan 30, 2020 at 23:53
  • 1
    $\begingroup$ (I've edited my answer to elaborate on what I think makes the book I recommend different from others I'm familiar with and in particular the ones you've asked about.) $\endgroup$
    – Misha Lavrov
    Commented Jan 31, 2020 at 0:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .