Connected graphs isomorphic to their own contraction

Question

Let $G = (V, E)$ be a simple, undirected graph with $|V|>2$, and let $S\subseteq V$ be a set with more than $1$ element. By $G/S$ we denote the graph obtained by collapsing $S$ to one point. More formally:

• $V(G/S) = (V \setminus S) \cup \{S\}$, and
• $E(G/S) = \big\{\{v,w\} \in E: v, w \notin S \big\}\cup \big\{\{v, \{S\}\}: v\in (V\setminus S)$ and there is $s \in S$ with $\{v,s\}\in E\big\}$.

We call a connected graph $G=(V,E)$ collapse-resistant $|V|> 2$ and if for all $S\subseteq V$ with $1<|S|<|V|$ we have $G \cong G/S$.

Clearly every infinite complete graph is collapse-resistant.

Question. Is every infinite connected collapse-resistant graph complete?

Answer 1

No. Let $G$ be the Rado graph (which is infinite, connected, and not complete), and $S$ a finite subset of the vertices of $G$ (because the Rado graph is countable). $G/S$ still has the extension property: for sets $U$ and $V$, there is a point in $G$ adjacent to all points in $U$, not adjacent to any points in $V$, and that is also not in $S$. (If either $U$ or $V$ contains the point $S$, we require the point in $G$ to be adjacent/not adjacent to all points in $S$). This point is adjacent in $G/S$ to all points in $U$, and not adjacent to any of the points in $V$. Any countable graph with this extension property is the Rado graph, so $G \cong G/S$.

Answer 2

No. Let $V = \mathbb{N}$ and $E = (0, i)$ for $i$ in $\mathbb{N}^*$ (a "star" graph where every vertex is connected to $0$).

If you collapse a subset containing $0$, the collapsed vertex can be mapped to $0$ and the remaining ones can be mapped to $\mathbb{N}^*$ as they are still all connected to $0$.

If you collapse a subset not containing $0$, you can map it to $1$ as it will only be connected to $0$. You can then map $0$ to $0$ and all the remaining vertices to $\mathbb{N} \setminus \{0, 1\}$

$G = (V, E)$ is collapse-resistant.

Answer 3

I add this answer to provide some variety, I believe this construction is collapse-resistant but the proof is not as easy and elegant as the other answers. Please comment if you find an error or gap in the proof !

Let $\mathbb{G}_f$ be the set of all finite graph. For $g \in \mathbb{G}_f$ a finite graph, let $\hat{g}$ be the union of a countable number of copy of $g$. Now let $G$ be the union of all $\hat{g}$ for $g \in \mathbb{G}_f$.

$G$ is not connected but it is collapse-resistant. When we collapse a finite subset of $G$, the resulting vertex will be connected to a finite number of vertices and be part a finite graph. It can be mapped to the corresponding finite graph from $G$. There will be a countable number of every finite graph remaining (not taking part in the collapse), so the result is still a countable number of every finite graph.

To get a connected graph, let us construct $\bar{G}$ by adding a vertex $o$ to $G$, connected to every other vertex.

$\bar{G}$ is connected and also collapse-resistant. If we collapse a subset $S$ containing $o$, the resulting vertex will be connected to all other vertices and can be mapped to $o$. For the remaining vertices ($\bar{G} \setminus \{o\}$), it is just as if we deleted $S \setminus \{o\}$, it will still result in a countable number of every finite graph. If we collapse a subset not containing $o$, it will work just the same as for $G$ (but with an added vertex $o$ connected to everything)

Note that this graph $\bar{G}$ is not the Rado graph, for example it has a vertex connected to every other vertex.