The python-graph-core project was hosted on google code but since google code has close (and even if the project has migrated on github) the package can't be installed using pip.
Also removing this (optional) dependency is not a bad thing...

Note that the package can still be installed on Ubuntu (at least 14.04) via the python-pygraph.

TODO: check if the function from scipy is equivalent

edit: the graph functions are available from scipy>=0.11.0