0
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ What about taking the disjoint union of all possible finite graphs, each one repeated countably many times? $\endgroup$
    – Thomas Bloom
    Commented Jul 28, 2021 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$
    – Dominic van der Zypen
    Commented Jul 28, 2021 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
    Commented Jul 28, 2021 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$
    – Mark Wildon
    Commented Aug 3, 2021 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$
    – Dominic van der Zypen
    Commented Aug 3, 2021 at 18:47

2 Answers 2

Reset to default
5
$\begingroup$

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

Improve this answer
$\endgroup$
3
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .