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.

There is also igraph, for Python, R, Ruby, and C.

http://igraph.sourceforge.net/