# Probability that a random graph will remain planar after adding an edge

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:
except:
open(filename,'w+').close()
file_lst = []
file_lst += [prob]
with open(filename,'w') as f:
json.dump(file_lst,f)

• I'm afraid $n = 10$ is a little small for experiments. – Yuval Filmus Aug 12 '18 at 2:27

Let $S$ be the set of planar graphs on $n$ vertices, and let $E(S,\overline{S})$ be the set of edges between $S$ and its complement, that is, the set of pairs $(G,e)$ where $G \in S$ and $G \cup \{e\} \notin S$. The edge-isoperimetric inequality states that $$\frac{|E(S,\overline{S})|}{|S|} \geq \binom{n}{2} - \log_2 |S|.$$ It follows that the probability that you're after is at most $$\frac{\log_2 |S|}{\binom{n}{2}-(3n-6)}.$$ It is known that $\log_2 |S| = O(n \log n)$ (see for example Gimenez and Noy, The number of planar graphs and properties of random planar graphs, and so we conclude that your probability is at most $O\left(\frac{\log n}{n}\right)$.
On the other hand, the same paper shows that with constant probability, a random planar graph has an isolated vertex. When this happens, there is $\Omega\left(\frac{1}{n}\right)$ probability to add an edge adjacent to it, leaving the graph planar. Hence your probability is at least $\Omega\left(\frac{1}{n}\right)$.