# Connected graphs isomorphic to their own contraction

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?

• Not a complete answer, but this is at least false if one restricts least false if one restricts only to contractions involving finitely many vertices. Construction: Given a graph $G$ let $C(G)$ be the union of all finite collapses of $G$ Then given a graph $G$, consider $G \cup C(G) \cup C(C(G)) \cdots$. This does not work in the obvious way if one allows countable contractions since one can take a contraction that involves taking a vertex from each level of the construction, but a similar argument then taking a union up to the smallest uncountable ordinal will then work. Commented Jan 14 at 16:52
• Wouldn't an infinite graph with no edges be collapse-resistant, for the same reason that an infinite complete graph is? Commented Jan 14 at 17:16
• Sorry I have to add "connected" graph Commented Jan 14 at 17:40
• Thanks @JoshuaZ - can you maybe make this into an answer? Commented Jan 14 at 17:42
• I would have called it contraction invariant, or possibly finite contraction invariant, since one could consider $\kappa$-contraction invariance, allowing the contraction of fewer than $\kappa$ many vertices. The concept makes sense in any relational structure, not just graphs. Also there is a weak and a strong form, depending on whether the new relation instances occur because of a single instance in $S$, as you defined, or whether you require all the instances with $S$ to hold. Paste bee's solution with the countable random graph is both weak and strong contraction invariant. Commented Jan 16 at 12:40

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

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.

• This was the simplest I could think of, I started with a covering tree because we want a connected graph, and then I realised the diameter of the graph will not grow when collapsing a subset. Turns out a tree of diameter 2 will do the trick ! Commented Jan 16 at 8:25
• I am trying to think of other graphs of diameter 2, but it is starting to look complicated as soon as you have vertices of degree different from 1 and infinity. Actually the Rado graph is of diameter 2 (according to wikipedia) so maybe you have to jump from the star graph directly to the Rado graph ? Commented Jan 16 at 8:31

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.