LaTeX for Graph Theory?

This perhaps isn't quite the answer you were looking for as it isn't TeX-centric, but Graphviz has always been (for me) the tool for drawing any kind graph with more then three vertices. The ability to export to PS or PDF is a plus and there are tons of wrappers so you can use your language of choice (personally I use pydot). Graphviz shines when you have many vertices that you would like to be arranged according to some pattern (several are provided).

That being said, for small graphs (or those with a tree-like dependency), nothing can beat tikz with the iteration of TeX directly into the document, though the verbosity sometimes is off putting.

Example of a simple tikz graph code:

\begin{tikzpicture}[shorten >=1pt,->]
  \tikzstyle{vertex}=[circle,fill=black!25,minimum size=12pt,inner sep=2pt]
  \node[vertex] (G_1) at (-1,-1) {1};
  \node[vertex] (G_2) at (0,0)   {2};
  \node[vertex] (G_3) at (1,-1)  {3};
  \draw (G_1) -- (G_2) -- (G_3) -- cycle;
\end{tikzpicture}

I'm the author of tkz-graph and tkz-berge. These packages are removed from my sites altermundus.fr and altermundus.com because I work actually to update them and to adapt them to pgf 2.0 and 2.1. I use some arithmetic tools and now these tools are in pgf 2.1 so it's better for me to update all the packages. There are also actually some problems of compatibility with my new packages tkz-base and euclide. If you want to use old versions of tkz-berge, don't install tkz-base. Problems come from arithmetic functions in tkz-arith and pgfmath. You can use my email from my site if you want an old version adapted to pgf 2.1

pgf is in the Ubuntu repositories, so for that you only need sudo apt-get install pgf. You do not need the newest version of tikz to use tkz-graph. Then create a directory in your home folder, say ~/texmf/tex/latex/tkz, and put tkz-graph.sty, tkz-arith.sty and tkz-berge.sty there. This should be enough. I have some examples of the usage of tkz-berge in my blog: http://graphtheoryinlatex.wordpress.com