Consider the elementary cellular automaton called Rule 110 (famous for being Turing complete):

It induces a map $ R: \mathbb{N} \to \mathbb{N}$ such that the binary representation of $ R(n)$ is the one of $ n$ after the application of Rule 110. For examples, $ R(0)=0$ , $ R(1)=3$ , $ R(2)=6$ and $ R(3)=7$ . See below the illustration for $ R(571)=1647$ :

There is an OEIS sequence computing $ R(n)$ for small $ n$ : A161903.

Lemma 1: For $ n>0$ we have $ R(n)>n$ and $ R^2(n)>2n$ .
Proof: Immediate.

Lemma 2: The equality $ R(n)=2n$ holds if and only if $ n=0$ .
Proof: Suppose the existence of $ n>0$ such that $ R(n)=2n$ . Then there is $ r>0$ such that $ n = \sum_{i=0}^r \epsilon_i2^i$ with $ \epsilon_i \in \{0,1 \}$ , $ \epsilon_r=1$ and $ R(n) = \sum_{i=0}^r \epsilon_i2^{i+1}$ . By applying Rule 110 to the portion $ (0,1,\epsilon_{r-1})$ which should give $ \epsilon_{r-1}$ , we deduce that $ \epsilon_{r-1} = 1$ . Next by applying Rule 110 to $ (1,1,\epsilon_{r-2})$ which should give $ \epsilon_{r-2}$ , we deduce a contradiction. $ \square$

Definition: Let $ \mathcal{G}$ be the graph with $ \mathbb{N}^{\star}$ as set of vertices and whose edges are the pairs $ \{n,R(n)\}$ .

Lemma 3: For any $ n>0$ , $ n$ and $ 2n$ are not in the same connected component of $ \mathcal{G}$ .
Proof: Suppose that $ n$ and $ 2n$ are in the same connected component. Then there is $ r_1,r_2>0$ such that $ R^{r_1}(n)=R^{r_2}(2n)$ . But $ R(2n) = 2R(n)$ , so $ R^{r_1}(n)=2R^{r_2}(n)$ . It follows by Lemma 1 that $ r_1 = r_2+1$ and so $ R(m) = 2m$ with $ m=R^{r_2}(n)$ , thus $ m=0$ by Lemma 2, contradiction. $ \square$

Lemma 4: For every $ n>0$ , there is a vertex of $ \mathcal{G}$ of degree $ \ge n$ .
Proof: The pattern of $ r \ge 2$ successive black cells (corresponding to the vertex $ 2^r-1$ ) is the image of any pattern of $ r-1$ cells without successive white cells, without three successive black cells and whose first and last cells are black, see for example below with $ r=27$ :

Clearly, for $ r$ large enough, the vertex $ 2^r-1$ has degree $ \ge n$ . $ \square$

Exercise: Show that $ |R^{-1} (\{ 2^r-1 \}) | = \sum_{2a+b = r} {a \choose b}$ , known as the Podavan sequence.

Corollary: The graph $ \mathcal{G}$ is not connected, and the degree of the vertices is not bounded above.
Proof: Immediate from Lemma 3 and 4. $ \square$

Question: Is the degree of the vertices bounded above on every connected component of $ \mathcal{G}$ ?