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

Let $G=(\omega,E)$ be a connected simple, undirected graph, where $E\subseteq [\omega]^2$.. For $m<n\in \omega$ we let $G/_{\{m,n\}}$ be the graph that we get from removing $n$, and $m$ gets all the neighbours from $n$. Formally, let $$G/_{\{m,n\}} = \big(\omega\setminus \{n\},\; (E\cap [\omega\setminus\{n\}]^2)\cup\{\{m, x\}: \{n, x\}\in E\} \land x\neq m\big).$$

We say that $G=(\omega, V)$ has the collapse-property if $G\cong G/_{\{m,n\}}$ for all $m<n\in\omega$.

What is an example of a non-complete, connected graph $G=(\omega,E)$ having the collapse-property?


1 Answer 1


There are many such graphs:

  • The (countable) random graph.

  • The "infinite depth-$1$ tree" given by $E=\{\{0,i\}: i>0\}$.

  • The "majestic sunflower" consisting of infinitely many $n$-cycles, for each $n$, joined at a common point.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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