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?

Solution 1:

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.

Solution 2:

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.

Solution 3:

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