Some useful examples of graphs

a repository of mathematical know-how

Some useful examples of graphs

Title: *

Area of mathematics: *

A comma-separated list of areas of mathematics to which this article applies. Use ">" to tag in a subcategory. Example: Analysis > Harmonic analysis, Combinatorics

Keywords:

A comma-separated list of keywords associated with this article. Example: free group

Used in:

A comma-separated list of examples of where this technique is used. Example: Cauchy-Schwarz inequality

Parent articles:		Order

Body:

[note article attention]This article should be generally cleaned up, and probably put into sections; the layout of images vs. text should also be prettified.[/note]

[note article contributions wanted]Additional examples of specific graphs or even graph families are needed; more than half of the page is currently devoted to random graphs.[/note]

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.

[[w:Petersen graph|The Petersen graph]] is a very unusual graph with many interesting properties, including:
[image petersen2.png|right|The Petersen graph]
* It is the smallest [[w:Snark (graph theory)|snark]]; furthermore, every snark contains the Petersen graph as a [[w:Graph minor|minor]].
* It is one of fourteen cubic [[w:Distance-regular graph|distance-regular graphs]], and one of either three or four [[w:Moore graph|Moore graphs]] of girth five.
* It is both [[w:Edge-transitive graph|edge-]] and [[w:Vertex-transitive graph|vertex-transitive]] (i.e., regular); it is the smallest connected vertex-transitive graph that is not a [[w:Cayley graph|Cayley graph]].
* It is the smallest known [[w:Hypohamiltonian graph|hypohamiltonian graph]].

[[w:Complete 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.
[image complete2.png|left|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 [[w:Edge coloring|edge chromatic number]] $n$.

[[w:Random graph|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 [[Applying the probabilistic method|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\H{o}s-R\'enyi 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 [http://terrytao.wordpress.com/2007/09/18/the-crossing-number-inequality/ 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 [[How to use Szemeredis regularity lemma|Szemer\'edi regularity lemma]] and similar results.
* [[w:Erdos-Renyi model|The Erd\H{o}s-R\'enyi 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\H{o}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\H{o}s-R\'enyi 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 [[w:Expander graph|interesting properties]].
*[[w:Rado graph|The Rado graph]].

This is a stub

A stub is an article that is not sufficiently complete to be interesting.

Notifications

File attachments

Changes made to the attachments are not permanent until you save this post. The first "listed" file will be included in RSS feeds.

	Delete	List	Description	Weight	Size
			/images/petersen2.png		13.9 KB
			/images/complete2.png		9.91 KB

Attach new file:

Images are larger than 640x480 will be resized. The maximum upload size is 1 MB. Only files with the following extensions may be uploaded: jpg jpeg gif png svg.

Revision information

Log message:

An explanation of the additions or updates being made to help other authors understand your motivations.

Some useful examples of graphs

Recent articles

Active forum topics

Recent comments