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?

• What about taking the disjoint union of all possible finite graphs, each one repeated countably many times? Jul 28 at 10:20
• Brilliant - this does work! Would you like to post it as an answer, so I can accept & upvote it? Or would you prefer that I delete the question. Maybe it is interesting for connected graphs Jul 28 at 10:22
• My answer to your similar question about deleting edges works as well: Take infinitely many disjoint edges together with infinitely many isolated vertices. Although unlike the Rado graph or Thomas Bloom's answer, this doesn't work for every non-edge. Jul 28 at 13:50
• I think the down-voters are being rather harsh: while the random graph gives a simple answer, it's hardly the most intuitive object one meets in mathematics. Aug 3 at 9:29
• Thanks @MarkWildon - I agree that the random graph is not a solution that jumps to the "pedestrian mathematician's" mind immediately Aug 3 at 18:47