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?
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
- Graph Theory: An Advanced Course (Graduate Texts in Mathematics) by Adrian Bondy and U.S.R. Murty,
- Modern Graph Theory (Graduate Texts in Mathematics) by B. Bollobás or
- Graph Theory (Graduate Texts in Mathematics) by Reinhard Diestel.
Also building on your background in discrete mathematics is invaluable. A book such as
- Concrete Mathematics: Foundation for Computer Science by Ronald L. Graham, Donald E. Knuth, Oren Patashnik
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).
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 ;)