The place I wish I had started at:
The Nature of Computation - Moore, Mertens
What I got (graduate coursework):
Graph Theory - Reinhard Diestel
A more encyclopedic treatment (most big results, no proofs):
Handbook of Graph Theory - Gross, Yellen
The Nature of Computation - Moore, Mertens
What I got (graduate coursework):
Graph Theory - Reinhard Diestel
A more encyclopedic treatment (most big results, no proofs):
Handbook of Graph Theory - Gross, Yellen