I used Graph Theory: Modeling, Applications, and Algorithms by Geir Agnarsson and Raymond Greenlaw as the basis of (part of) a masters course. I was happy with the book, although I didn't go all the way through it. It starts slowly yet covers a decent range of topics at a relatively slow pace.
I also used Graph Theory: An Advanced Course by Adrian Bondy and U.S.R. Murty (already mentioned) as a source of challenge exercises. It's a great resource.
