1.4 The Collatz Graph
The Collatz graph \(\mathcal{G}\) is a directed graph on \(\mathbb {N}\) with an edge from \(n\) to \(T(n)\) for all \(n \in \mathbb {N}\). We consider its associated simple undirected graph \(\mathcal{G}'\).
Two distinct vertices \(a, b\) are adjacent in \(\mathcal{G}'\) if and only if \(b = T(a)\) or \(a = T(b)\).
Immediate from the definition of the simple graph associated with a directed graph.
For any \(k, n \in \mathbb {N}\), \(T^k(n)\) is reachable from \(n\) in \(\mathcal{G}'\).
By induction on \(k\), following the edges \((T^i(n), T^{i+1}(n))\).
If \(T^i(a) = T^j(b)\) and \(b\) is adjacent to \(c\) in \(\mathcal{G}'\), then there exist \(i', j'\) such that \(T^{i'}(a) = T^{j'}(c)\).
If \(c = T(b)\), then \(T^i(a) = T^j(b)\), so \(T^{i+1}(a) = T(T^i(a)) = T(T^j(b)) = T^{j+1}(b) = T^j(c)\). If \(b = T(c)\), then \(T^i(a) = T^j(b) = T^j(T(c)) = T^{j+1}(c)\).
If \(a\) and \(b\) are reachable in \(\mathcal{G}'\), then they have a common descendant under \(T\), i.e., there exist \(i, j\) such that \(T^i(a) = T^j(b)\).
By induction on the path length between \(a\) and \(b\), using Lemma 42.
The Collatz graph \(\mathcal{G}\) restricted to positive integers is weakly connected (i.e., any two \(a, b \ge 1\) are reachable in \(\mathcal{G}'\)) if and only if the Collatz conjecture holds.
(\(\Rightarrow \)) Assume connectivity. For any \(n \ge 1\), \(n\) is reachable from 1. By Lemma 43, there exist \(i, j\) such that \(T^i(n) = T^j(1)\). Since 1 is in a cycle \(\{ 1, 2\} \), \(T^j(1) \in \{ 1, 2\} \), so \(T^i(n)\) eventually hits 1. By Lemma 115, \(n\) eventually hits 1 under \(C\). (\(\Leftarrow \)) Assume the Collatz conjecture. For any \(n \ge 1\), \(n\) eventually hits 1 under \(C\), and by Lemma 116, it also hits 1 under \(T\). By Lemma 41, \(n\) is reachable from 1 in \(\mathcal{G}'\). Thus any \(a, b \ge 1\) are both reachable from 1, and hence reachable from each other.