The big three are networkx, igrpah, and python-graph. Each has it's advantages and disadvantages, so test each one a bit if you are doing serious graph work in python. For toy/casual problems I would recommend python-graph or networkx.