12
$\begingroup$

I would like to learn Graph Theory from the beginning. It seems to me that one does not need to be familiar with many abstract type subjects to be able to understand the more basic concepts of graphs.

  1. Which subjects should one know prior to learn Graph Theory at the introductory level?

  2. And which book or lecture notes would you advise to learn it?

6 Answers 6

15
  1. (a) Basic logic + set operations almost goes without saying (e.g. logical conjunction / set intersections; also equivalence classes, sets and relations obtained by modding out subsets, etc).

    (b) Depending on how 'basic' you mean, you may or may not derive benefit from linear algebra (for playing with adjacency matrices), probability theory (for applying the probabilistic method, natch), elementary number theory (e.g. arithmetic modulo N) and experience with asymptotic analysis (knowledge of what O(N), o(N), ω(N), etc. refer to and how to play with them).

  2. I found Diestel's text quite nice. (Furthermore, it is freely available from his website). I also found that undoing his proofs-by-contradiction provides good exercise.

  • 1
    Niel, thanks for this; my familiarity with graph theory is due to my knowledge that depictions of molecules in chemistry can be encoded as appropriate adjacency matrices, but I have yet to figure out how to apply what I already know in linear algebra to graph theory. I really should get off my lazy bum and devote some time to studying graph theory thoroughly.2010-09-10
  • 0
    +1 For the subjects one should know and your advice. I know the concepts/notation of O(N), o(N), ω(N) but I have not much experience in playing with them.2010-09-10
  • 1
    Diestel's book is a graduate level book. Is that the type of book someone who wants to learn it from the beginning should use?2011-11-28
  • 0
    @Graphth: If you look at the introductory chapter, you will find that it starts from the most elementary concepts. In each chapter, it takes some time to introduce any new concepts. When I started studying graph theory in earnest (as opposed to merely knowing lists of graph-theoretic definitions), Diestel's was the text I used. It won't assume that you need your hand held, but it's not going to rush headlong into deep shark-infested waters either. I found it generally pretty well written.2011-11-28
  • 0
    @NieldeBeaudrap You may be right. I own the book but have never looked at it (my bad). I use "Graphs and Digraphs" by Chartrand, Lesniak, and Zhang, and it's very good. I have heard from friends that Diestel's doesn't give many examples and is hard to read if you've never studied graph theory before.2011-11-28
5

Graph Theory is indeed a very quick starting subject in the sense that one does need to have studied calculus and other mathematical subjects to get started. However, there are lots of books that are specialized towards particular purposes: applications in general, network applications, distances in graphs, etc.

One book that I think has nice balance is:

Introduction to Graph Theory (Second edition) by Douglas West, Prentice-Hall, 2001.

2

You don't need more than knowledge of basic notations in Mathematics to read a basic book on Graph Theory. However, some experience in mathematics is helpful, even if the material is not used directly.

My favorite books for "pure" graph theory is "Graph Theory" by Harary and "Modern Graph Theory" by Bollobas. They also delve into algebraic graph theory in later chapters and for that you'll need some basic linear algebra and group theory. Also, graph theory is widely used in computer science and so, for example, many chapters in the "Introduction to algorithms" by Corman and co. deal with algorithms on graphs (an interesting subject by itself but maybe not what you have in mind).

  • 2
    "Modern Graph Theory" by Bollobas is not really an introductory level book.2010-09-10
  • 1
    It's not an easy book, but most of it requires little knowledge of advanced topics in mathematics.2010-09-10
2

For easy read:

  1. Combinatorics and Graph Theory by Harris

  2. Introduction to Graph Theory by Wilson

2

I thought about this question for a graph theory course I'm teaching. Prerequisites would be mathematical proof technique (induction, proof by contradiction), and linear algebra (determinants, eigenvalues).

The book I eventually chose was Bondy and Murty's Graph Theory. It's a bit dry, but it's mathematically very nice, it has a lot of material if you want to delve deeper (you won't throw it away after the "course" is over), and it's quite readable. It's also cheap, and in fact available for free online from Springer's website.

  • 0
    Daniel: what you mean by "dry"?2011-11-28
1

I am learning some graph theory myself as an independent study in college.

I started with a very simple, but informative text, Introductory Graph Theory by Chatrand. It is a Dover book, and can be bought for very cheap on Amazon. I then went to my university library and took out Modern Graph Theory by Bollobas. It is not an easy book, but it is incredibly clear and informative.

There are also great introductions to be found online.

Here is a rather lengthly sample of Bollobas's Modern Graph Theory: http://books.google.com/books?id=SbZKSZ-1qrwC&printsec=frontcover&source=gbs_slider_thumb#v=onepage&q&f=false

  • 0
    Thanks! Since Dover books are inexpensive I intend to buy it.2010-09-12