Introduction to Graph Theory (Dover Books on Mathematics)

I think I liked the original title, Dots and Lines, better. However, Introduction to Graph Theory was what I was searching for. This book is getting close to 50 years old. However, the basics of graph theory still remain. Perhaps the only part that caught me off guard was the mention that the 4-color problem had not been proved. Alas, when I got to the end, the author corrected this with mention of the proof. (It came out right around the time this book was published.) 

The book targets a more general audience than just mathematicians. However, it does not skimp on rigor. The opening chapter starts with an introduction to "pure mathematics". The author desires that we can find the joy in math that mathematicians find, and not get bogged down with mechanics.  There are plenty of detailed proofs and exercises in the book. At times the book gets pretty deep into the nitty-gritty. However, it will often then bounce back out to more easily acceptable prose. I found it to be a good introduction to graph theory. It contained enough detail to fill in basic understanding gaps and seems to have a good chunk of problems to go through on a re-read.