Graph Theory in Sage is a presentation by William Stein of some of the graph capabilities of Sage.
I mention it because there has been discussion on the Neo4j mailing list about learning graph theory and this may be helpful in that regard.
There is a Sage worksheet that has all the formulas and values used in the presentation.
You can also download the video.
You will have to experience it for yourself but I thought the help feature on graphs was most impressive.
Sage will help you get your feet on the ground with formal graph theory.