# Prerequisites for learning (basic) Graph Theory

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?

-

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.

-
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. – J. M. Sep 10 '10 at 12:22
+1 Diestel's text is excellent! – alext87 Sep 10 '10 at 12:38
+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. – Américo Tavares Sep 10 '10 at 12:56
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? – Graphth Nov 28 '11 at 15:30
@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. – Niel de Beaudrap Nov 28 '11 at 15:46

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.

-

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

-
"Modern Graph Theory" by Bollobas is not really an introductory level book. – alext87 Sep 10 '10 at 12:15
It's not an easy book, but most of it requires little knowledge of advanced topics in mathematics. – Gadi A Sep 10 '10 at 12:38

1. Combinatorics and Graph Theory by Harris

2. Introduction to Graph Theory by Wilson

-

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

-
Thanks! Since Dover books are inexpensive I intend to buy it. – Américo Tavares Sep 12 '10 at 11:01

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.

-
Daniel: what you mean by "dry"? – Damian Sobota Nov 28 '11 at 14:39