A Survey of Graph Theory and Applications in Neo4J by Geoff Moes.
A great summary of resources on graph theory along with a two part presentation on the same.
Geoff mentions: Graph Theory, 1736-1936 by Norman L. Biggs, E. Keith Lloyd, and Robin J. Wilson, putting to rest any notion that graphs are a recent invention.
Enjoy!