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?

  • 2
    $\begingroup$ What about taking the disjoint union of all possible finite graphs, each one repeated countably many times? $\endgroup$ Jul 28 at 10:20
  • $\begingroup$ 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 $\endgroup$ Jul 28 at 10:22
  • $\begingroup$ 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. $\endgroup$
    – Louis D
    Jul 28 at 13:50
  • 1
    $\begingroup$ 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. $\endgroup$ Aug 3 at 9:29
  • $\begingroup$ Thanks @MarkWildon - I agree that the random graph is not a solution that jumps to the "pedestrian mathematician's" mind immediately $\endgroup$ Aug 3 at 18:47

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'.


For a connected counterexample you could take the Rado graph (https://en.wikipedia.org/wiki/Rado_graph). It shouldn't be too hard to prove that when you add an edge, the resulting graph will still satisfy the extension property, which characterizes the Rado graph.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.