For any set $X$ we let $[X]^2 = \big\{\{x, y\}: x\neq y \in X\big\}$. Consider the following statement:



> 
> (S) : If $G =(V,E)$ is a simple, undirected graph such that $E \neq [X]^2$, then there is $e^\* \in [X]^2 \setminus E$ such that $G \not \cong (V, E\cup\{e^\*\})$.
> 
> 
> 


For finite graphs, (S) is true since adding any edge changes the degree sequence. Does (S) hold for infinite graphs as well?



Edge-adding conjecture for graphs
No - for a countexample, take the disjoint union of all possible finite graphs, each repeated countably many times.


There is a similar counterexample even if we ask that the graph be connected - just add all possible edges between vertices from different 'copies'.


