It is going to be the first time for me to learn graph theory. What kind of mathematical background do I need to prepare master theses about this subject in following years? Which subjects should be reviewed and is there any book that covers all of them?

  • 2
    $\begingroup$ The nice thing about Graph theory is that you really don't need much background to start it and that background is usually given in an introductory chapter or appendix of some books (e.g. West's Graph Theory book). $\endgroup$ – Kaveh Jan 26 '11 at 0:51

There are plenty of good books on graph theory. Start with something introductory like Graph Theory: Modeling, Applications and Algorithms, or one of the many more or less equivalent books at that level. Then move onto something more advanced, such as

Also building on your background in discrete mathematics is invaluable. A book such as

would be provide you will a solid grounding.

Most of these books would then serve as references for life.

See also this question What kind of mathematical background is needed for complexity theory?, as much of the background will overlap, in particular wrt combinatorics and stochastics (probability and statistics).

  • 1
    $\begingroup$ Also Introduction Graph Theory by D.B. West. $\endgroup$ – Kaveh Jan 26 '11 at 0:49

Linear algebra is very useful for certain areas of graph theory (including some fairly advanced linear algebra). It can also be very useful in practice -- linear algebra and graph theory are two of the things which make Google work. And elementary linear algebra is used in enough places that you might want to learn it in any case.


I don't think you really need too much.

You should have some experience proving proofs of theorems (mathematical induction) and understand what recurrences are.

You will find some good Discrete Mathematics courses containing Graph Theory ;)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.