Add and subtract new edges with the arrow keys, or enter specific parameters with contols below.

click to reset

Paul Erdös and Alfred Renyi did a lot of work on characterizing the structure of random graphs. This is tool to visualize some of their observations.

A random graph with $n$ vertices and an edge density of $p$ is often written as $$G_{(n,p)}$$ We can construct such a graph $G$ by selecting from each potential edge with probability $p$ or by selecting $j$ random edges. In the latter case, we can describe $p$ in terms of $j$ and $n$ as $$p = {j \over{\binom{n}{2}}}$$ Erdös and Renyi noticed (and proved) that whenever $p < \frac{1}{n}$, $G$ is usually comprised of a bunch of small tree-like components, but if $p > \frac{1}{n}$ there quickly emerges a single large connected subgraph. They called the resulting subgraph the "giant component".