Some useful examples of graphs

This article is in need of attention. This article should be generally cleaned up, and probably put into sections; the layout of images vs. text should also be prettified.

This article could use additional contributions. Additional examples of specific graphs or even graph families are needed; more than half of the page is currently devoted to random graphs.

This article contains examples of graphs and graph-theoretic constructions that may be used to test the truth or falsity of statements in graph theory.

The Petersen graph is a very unusual graph with many interesting properties, including:

The Petersen graph

It is the smallest snark; furthermore, every snark contains the Petersen graph as a minor.
It is one of fourteen cubic distance-regular graphs, and one of either three or four Moore graphs of girth five.
It is both edge- and vertex-transitive (i.e., regular); it is the smallest connected vertex-transitive graph that is not a Cayley graph.
It is the smallest known hypohamiltonian graph.

The complete graph $K_n$ is defined as the graph with vertex set $\{0, 1, \ldots, n-1\}$ and an edge between every pair of distinct vertices.

The complete graph K6

If a graph property is closed under taking subgraphs, and it is true for complete graphs, then it is true for all finite graphs.
$K_n$ has $n(n-1)/2$ edges, the most of any graph on $n$ vertices.
$K_n$ for odd $n$ has maximum degree $n-1$ and edge chromatic number $n$ .

Random graphs often have unexpected properties; it is often the case that we can show that a random graph has a certain property with high probability but cannot construct an explicit graph (or family of graphs) with that property. At the highest level of generality, a random graph is simply a graph drawn from some probability distribution on graphs, but there are several models with interesting properties that are much easier to work with. Discussion of a few of these models will follow after a general discussion.

General discussion of random graphs:
- If you can show that a random graph drawn from some distribution has some property with positive probability, then it follows that there exists a graph with that property. (This observation is the basis of the probabilistic method.) Thus, random graphs are often useful as counterexamples.
- If you can show that a random graph has some property with probability $1$ (in the limit), then it is sometimes the case that all graphs have this property; however, the opposite is very often true. For example, the random graph $G(3n, n^2)$ (see the Erdős-Rényi model below) is connected with probability $1$ , but it is by no means the case that every graph with $3n$ vertices and $n^2$ edges is connected.
- There are cases in which statements about random graphs can be used to prove statements about all graphs; for instance, as amplification in the proof of the crossing number inequality. Similarly, if a property holds both for random graphs and for highly "structured" graphs, it can in some cases be extended to all (or almost all) graphs using the Szemerédi regularity lemma and similar results.
The Erdős-Rényi random graph model $G(n,p)$ is, intuitively, the random graph with vertex set $\{0, 1, ..., n-1\}$ such that the probability that two distinct vertices are adjacent is equal to $p$ and every pair of such events is independent. (Equivalently, it is drawn from the distribution where the probability of the event $\{G_0\}$ , where $G_0$ is a graph with $n$ vertices and $m$ edges, is $p^m(1-p)^{{n \choose 2}-m}$ ).
- A very similar model is $G(n, M)$ , which is drawn uniformly from the set of graphs on $n$ vertices with $M$ edges. In fact, for many natural graph properties, $G(n, p)$ and $G(n, {n \choose 2}p)$ behave exactly the same way. While the first model is usually easier to analyze, the second model can be useful in some cases or as an alternative way to think about the first.
- For many graph properties, there is a threshold function $f(n)$ such that, if $p >> f(n)$ , $G(n, p)$ has the property with probability $1$ , whereas if $p << f(n)$ , $G(n, p)$ does not have the property with probability $1$ . For instance, $G(n, 2 \frac{ln n}{n})$ is almost surely connected, but $G(n, \frac{1}{2} \frac{ln n}{n})$ is almost surely not connected.
- Even when a random graph does not have a certain property, it may "almost have it", and you may be able to obtain such a graph by modifying $G(n, p)$ slightly. An argument along these lines was used by Erdős in his famous proof that there exist graphs with arbitrarily high girth and chromatic number.
If you are studying sparse graphs, then the Erdős-Rényi model has some undesirable properties; for instance, the maximum degree of $G(n, p = k/n)$ is not necessarily bounded. A good model for random sparse graphs is to choose a $d$ -regular graph on $n$ vertices uniformly at random; these graphs are known to have a number of interesting properties.
The Rado graph.

7282 reads
Subscribe

Comments

More examples

Thu, 23/04/2009 - 08:37 — JoseBrox

You can also add trees and forests, and complete bipartite graphs $K_{n,m}$ . 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 — gowers

A 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 edge-graphs of polyhedra, the usual graph on $\Z^2$ , 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 $\Z^2$ , are infinite but not massively different in flavour from finite graphs such as big grids. Others, such as the graph where you well-order the reals and take all pairs $(x,y)$ such that the usual ordering agrees with the well-ordering, are much more infinitary and probably belong elsewhere.

My feeling on infinite

Thu, 23/04/2009 - 14:08 — brownh

My feeling on infinite graphs, for what it's worth, is that they should probably be included here if the graph-theoretical perspective sheds some basic insight on the infinite structure, or if they can give some insight into finite graphs – so the usual graph on $\Z^2$ 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.

Post new comment

(Note: commenting is not possible on this snapshot.)