I found "A Logical Approach to Discrete Math" by Gries and Schneider to be delightful. It teaches discrete math using formal logic as the basis of the whole system.
Concrete Mathematics by Don Knuth. If you want specifically graph theory, I'd suggest Introduction to Graph Theory by Doug West.
I found Concrete Mathematics to be a bit dense and not very suited for self learners like me. Also it does not cover the basics like proofs, counting etc.
I've read good reviews of Susana Epp's Discrete Mathematics With Applications, and I liked what I read in a preview. It's expensive, though, so I'm waiting for the international edition (about 1/3 the cost), which is due out next month.