Reddit reviews Pearls in Graph Theory: A Comprehensive Introduction (Dover Books on Mathematics)

1. LOVE this book: Pearls in Graph Theory
   
   Chapters are short and engaging. Great exercises. Very visual and creative which should make mathematical structure more appealing to a lay person.
   
   
2. Winning Ways for your Mathematical Plays by Berlekamp, Conway, and Guy may not satisfy your rigorous criterion but should blow the mind of anyone who thinks of math as primarily computational tools.
   
   
3. Visual Complex Analysis by Needham is an amazing book, but may be too technically difficult (particularly if her calculus is rusty).

Specifically Graph Theory? Pearls In Graph Theory was the one that I used in my undergraduate course. It covers some algorithms and the theory behind completeness, infinite lattices, etc. Fun stuff!

If you want a more combinatorial view of things (ie: not so specialized with regards to Graph Theory), I highly recommend Brualdi's Introductory Conbinatorics as bucket1004 said. I also used that one for my combinatorics course and I loved it.

Disclaimer: There's some errata in the edition that I used. I'm not so sure how much better the new editions are.