13
$\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.

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

  • 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