Experiment

Random Graphs G(n, m)

Observe Erdős–Rényi G(n, m) graphs as edges are added one by one and relate them to the equivalent G(n, p).

Edge process intuition: this is the $G(n, m)$ analogue of Erdős–Rényi—edges are shuffled and added one by one until exactly $m$ exist. Watching the process lets you relate discrete edge counts to the matching $G(n, p)$ probabilities.

Parameters: set n via `Number of vertices`, choose total edges m, control animation `Speed (ms)`, and fix the RNG with `Seed` to replay runs.

Parameters
Tracking 80 edge additions (435 possible edges). p estimate = m / (n choose 2).
Edge additions
Step Edges added p estimate Largest component # Components Triangles Connected? Isolated vertices
1 1 0.002 2 29 0 No 28
2 2 0.005 2 28 0 No 26
3 3 0.007 2 27 0 No 24
4 4 0.009 2 26 0 No 22
5 5 0.011 2 25 0 No 20
6 6 0.014 2 24 0 No 18
7 7 0.016 2 23 0 No 16
8 8 0.018 2 22 0 No 14
9 9 0.021 3 21 0 No 13
10 10 0.023 3 20 0 No 12
11 11 0.025 4 19 0 No 12
12 12 0.028 4 18 0 No 12
13 13 0.030 5 17 0 No 11
14 14 0.032 5 16 0 No 9
15 15 0.035 6 15 0 No 8
16 16 0.037 6 14 0 No 7
17 17 0.039 8 13 0 No 7
18 18 0.041 8 12 0 No 7
19 19 0.044 8 11 0 No 5
20 20 0.046 10 10 0 No 5
21 21 0.048 10 9 0 No 4
22 22 0.051 13 8 0 No 4
23 23 0.053 13 8 0 No 4
24 24 0.055 21 7 0 No 4
25 25 0.058 21 7 0 No 4
26 26 0.060 22 6 0 No 3
27 27 0.062 23 5 0 No 2
28 28 0.064 26 4 0 No 2
29 29 0.067 26 4 0 No 2
30 30 0.069 26 4 0 No 2
31 31 0.071 28 3 0 No 2
32 32 0.074 28 3 0 No 2
33 33 0.076 28 3 0 No 2
34 34 0.078 28 3 0 No 2
35 35 0.081 28 3 1 No 2
36 36 0.083 28 3 1 No 2
37 37 0.085 28 3 1 No 2
38 38 0.087 28 3 1 No 2
39 39 0.090 28 3 1 No 2
40 40 0.092 28 3 1 No 2
41 41 0.094 28 3 1 No 2
42 42 0.097 29 2 1 No 1
43 43 0.099 29 2 1 No 1
44 44 0.101 29 2 1 No 1
45 45 0.103 29 2 2 No 1
46 46 0.106 30 1 2 Yes 0
47 47 0.108 30 1 3 Yes 0
48 48 0.110 30 1 3 Yes 0
49 49 0.113 30 1 3 Yes 0
50 50 0.115 30 1 3 Yes 0
51 51 0.117 30 1 3 Yes 0
52 52 0.119 30 1 3 Yes 0
53 53 0.122 30 1 3 Yes 0
54 54 0.124 30 1 3 Yes 0
55 55 0.126 30 1 4 Yes 0
56 56 0.129 30 1 4 Yes 0
57 57 0.131 30 1 8 Yes 0
58 58 0.133 30 1 8 Yes 0
59 59 0.136 30 1 10 Yes 0
60 60 0.138 30 1 11 Yes 0
61 61 0.140 30 1 11 Yes 0
62 62 0.142 30 1 12 Yes 0
63 63 0.145 30 1 12 Yes 0
64 64 0.147 30 1 13 Yes 0
65 65 0.149 30 1 13 Yes 0
66 66 0.152 30 1 14 Yes 0
67 67 0.154 30 1 14 Yes 0
68 68 0.156 30 1 14 Yes 0
69 69 0.159 30 1 14 Yes 0
70 70 0.161 30 1 15 Yes 0
71 71 0.163 30 1 18 Yes 0
72 72 0.166 30 1 18 Yes 0
73 73 0.168 30 1 18 Yes 0
74 74 0.170 30 1 18 Yes 0
75 75 0.172 30 1 18 Yes 0
76 76 0.175 30 1 22 Yes 0
77 77 0.177 30 1 22 Yes 0
78 78 0.179 30 1 22 Yes 0
79 79 0.182 30 1 23 Yes 0
80 80 0.184 30 1 23 Yes 0
Phase transitions
Observed
Event Theoretical Observed
First cycle appears 0.033 0.053
Graph becomes connected 0.113 0.106
Isolated vertices disappear 0.113 0.106
Triangle appears 0.063 0.081
Giant component ≥ 50% nodes — 0.055
Theoretical markers
  • p = 0.0333 First cycle ~1/n
  • p = 0.0627 First triangle (p ≈ d/n, d ≈ 1.82)
  • p = 0.1134 Connectivity (log n / n)
  • p = 0.1134 Isolated vertices disappear (log n / n)
  • p = 0.5 Dense regime 0.5