If I add or remove a single edge from a graph, does the genus change by at most a constant amount? More precisely,
A graph parameter is a function $f$ that maps graphs to a range $\{1, \cdots, m\}$ and that assigns the same value to isomorphic graphs. Examples include number of cycles, chromatic number, cardinality of maximum matching, maximum cut, and maximum independent set. A graph parameter is said to be $\Delta$-robust if for any $G$, $f(G)$ changes by at most $\pm \Delta$ if an edge is added to or deleted from $G$.
My question is the following: is the genus of a graph a $C$-robust for some fixed constant $C$? I would imagine this is not true but I haven’t been able to construct any good counter examples.
Adding a single edge to a graph cannot make its genus increase by more than $1$.
Suppose the original graph is drawn on a surface of genus $n$. Then there is a surefire way to draw the extended graph on a surface of genus $n+1$ -- namely, just add a handle to the surface that goes directly from the vicinity of one endpoint to the vicinity of the other endpoint, and draw your new edge along that, bypassing everything else.
Thus, the genus of a graph is $1$-robust.