This article contains useful examples of graphs
The Petersen graph is a very unusual graph with many interesting properties, including:

It is the smallest snark; furthermore, every snark contains the Petersen graph as a minor.

It is one of fourteen cubic distanceregular graphs, and one of either three or four Moore graphs of girth five.

It is both edge and vertextransitive (i.e., regular); it is the smallest connected vertextransitive graph that is not a Cayley graph.

It is the smallest known hypohamiltonian graph.
The complete graph is defined as the graph with vertex set and an edge between every pair of distinct vertices.

If a graph property is closed under taking subgraphs, and it is true for complete graphs, then it is true for all finite graphs.

has edges, the most of any graph on vertices.

for odd has maximum degree and edge chromatic number .
Comments
More examples
Thu, 23/04/2009  08:37 — JoseBroxYou can also add trees and forests, and complete bipartite graphs . Maybe pseudoforests and cycle graphs could be interesting too.
That's just if we don't want to enter the realm of possibly infinite directed multigraphs with loops ;P
A general comment about the
Thu, 23/04/2009  09:04 — gowersA general comment about the organization of this article. I think I'd suggest something like this.
1. Elementary families of graphs. (Would include complete graphs, complete bipartite graphs, paths, cycles, rooted binary trees, the discrete cube, and probably more.)
2. Elementary graphs derived from other structures. (Would include things like edgegraphs of polyhedra, the usual graph on , and so on.)
3. "Sporadic" graphs with interesting properties, such as the Petersen graph.
Then there are more general ways of coming up with graphs, such as random graphs, Cayley graphs, geometric graphs, interval graphs, etc. (Some of the above graphs can be realized as Cayley graphs, of course, but this doesn't matter.) Here, I think the best thing would be to have a rather brief discussion of what can be done and when one expects these methods to be useful, followed by links to other pages. For example, both random graphs and Cayley graphs are huge topics.
It's not quite clear to me what we should do about infinite graphs. Some infinite graphs, such as the usual graph on , are infinite but not massively different in flavour from finite graphs such as big grids. Others, such as the graph where you wellorder the reals and take all pairs such that the usual ordering agrees with the wellordering, are much more infinitary and probably belong elsewhere.
My feeling on infinite
Thu, 23/04/2009  14:08 — brownhMy feeling on infinite graphs, for what it's worth, is that they should probably be included here if the graphtheoretical perspective sheds some basic insight on the infinite structure, or if they can give some insight into finite graphs – so the usual graph on might qualify because it does encapsulate many of the properties of grids, but the obvious graph derived from the Leech lattice probably wouldn't qualify, since despite its retaining many of the interesting properties of the Leech lattice, it doesn't actually tell you anything that the lattice itself doesn't already. I'm not really all that familiar with infinite graph theory, though, so I'll probably leave that area mostly alone for now.
I agree with you generally about the organization of the article. I'm a little worried that the boundaries between (2) and the other classes seem kind of nebulous, but that difficulty will probably resolve itself over the course of editing the article.