# Crossing number of a graph with an additional edge

Suppose that I have a graph $$G=(V,E)$$ with a known crossing number, say $$n=cr(G)$$. I would like to show that the graph $$G'=(V,E\cup e')$$ obtained by adding an edge $$e'$$ to $$G$$ that was not previously in it satisfies the relation:

$$cr(G')\leq cr(G)+1.$$

Is this true in general? Or at least for the family of complete graphs $$K_{m,n}$$?

• Can't be true in general if I'm understanding correctly: crossing number is at least $e^3 / (29 v^2)$ when $e > 7v$ from the crossing number inequality (wikipedia; $e$ is # edges, $v$ is # vertcies). Pick say $v=20, e = 141$. Start with a graph on $v$ nodes and 0 edges. Add $e$ edges one-by-one. Overall crossing number increased from 0 to $e^3 / (29v^2) \ge 241 > 141 = e$. So crossing number must have increased by 2 at least once. Not sure about the $K_{m, n}$ case. – xmq May 9 at 20:09