According to this answer, a random graph on $n$ vertices is a graph which has each of the $n\choose2$ edges independently with probability $1/2$ each. The probability of at most $3n-6$ edges (which is a necessary condition for planarity) is: $$2^{-n(n-1)/2}\sum_{k=0}^{3n-6}{n(n-1)/2\choose k}$$
Therefore, the plot for this equation is:
If I choose a random graph with 10 vertices, what is the probability that it will remain planar after adding an edge between two randomly chosen vertices?
To be more clear:
Consider event $P_{1}$, the event of choosing a planar graph $G_{1}$ in the universe $U_{10}$ of graphs with 10 vertices.
Consider a subset $S$ of the universe of graphs with 11 vertices $U_{11}$ conditionally defined by the graph $G_{1}$ we got in event $P_{1}$ in this way: $S$ is formed by all possible graphs that can result from adding one edge to $G_{1}$.
And then finally consider event $P_{2}$, the event of choosing a planar graph in the universe $S$ defined in the previous step.
Therefore I want to know what is the probability of event $P_{2}$.
Possible solution:
I followed D.W.'s advice below and wrote a small simulation. According to the code, the probability of choosing a planar graph of 10 vertices is 0.0915 ( 9,15% ) and the probability of a given planar graph of 10 vertices remaining planar after adding one random edge is 0.6140 ( 61,40% ).
#!/usr/bin/python3
import planarity
from itertools import combinations
import random
from multiprocessing import Process, Manager, Pool, cpu_count
import json
nodes = [str(x) for x in range(10)]
edges = list(combinations(nodes,2))
tests = 10**6
filename = 'results.json'
runs = 100
def make_test():
while 1:
chosen_edges = list(filter(lambda x: x != None, [x if random.choice([0,1]) else None for x in edges]))
if planarity.is_planar(chosen_edges):
break
extra_edge = random.choice( list(set(edges) - set(chosen_edges)) )
chosen_edges += [extra_edge]
return planarity.is_planar(chosen_edges)
if __name__ == '__main__':
for i in range(runs):
with Pool(processes=cpu_count()) as pool:
results = [ pool.apply_async(make_test, ()) for i in range(tests) ]
lst = [ res.get(timeout=1) for res in results ]
pool.close()
pool.join()
n = len(lst)
p = len(list(filter(lambda x: x != False, lst)))
prob = ( p / n )
print(prob)
try:
with open(filename,'r') as f:
file_lst = json.load(f)
except:
open(filename,'w+').close()
file_lst = []
file_lst += [prob]
with open(filename,'w') as f:
json.dump(file_lst,f)
