I saw some recommendations for Combinatorics and Graph Theory by Harris, Hirst, and Mossinghoff so I picked up a copy of it. I'm more interested in the math than I am in applications at this point though I'll probably circle back to them later.
I've worked through Enderton's "Elements of Set Theory" so I believe I understand your question, and I think Harris, Hirst & Mossinghoff's "Combinatorics and Graph Theory" is exactly what you're looking for.
It doesn't have any prerequisites, it's a gentle introduction to the material; but is completely rigorous, reaches a solid level, and suggests many nice exercises.
I liked the Harris, Hirst, Mossinghoff text that I used for an undergrad class. It's a solid intro that builds from the very beginning, and at times has an almost irreverent writing style that references everything from Shakespeare to Kevin Bacon.
This may help, I really like this book: https://www.amazon.com/Combinatorics-Graph-Theory-Undergraduate-Mathematics/dp/0387797106