Skip to main content
2 of 2
added 219 characters in body
Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104

If there is an infinite path then there is also a finite path using two of $a,b,c,d$ as endpoints. However the converse is not true, so the question makes sense. There is some ambiguity about how explicitly one knows the graph.

I will give a graph $H$ which is a disjoint union of paths and has an infinite path exactly if the Collatz $3n+1$ conjecture is false due to an unbounded trajectory. I will then make it into a tree $G$ (plus isolated vertices perhaps) by adding 4 more vertices $a,b,c,d$ which are in an infinite path exactly if $H$ has such a path. I am sure this is much more complicated than it needs to be, but it does work.

Define the function $f$ on positive integers by $f(n)=\frac{n}{2}$ for $n$ even and $f(n)=3n+1$ for $n$ odd. The conjecture is that iteration always arrives at $1.$ Equivalently, for all $n \gt 1$ there is in the list $n,f(n),f(f(n))=f^2(x),f^3(x), \cdots$ a number less than $n.$ If there is a counter-example $n,$ then it is odd and either the sequence above enters a cycle not including $1$ or is the start of a trajectory which increases without bound. It is this second case that would lead to an infinite path .

The vertices of the graph $H$ will be all integer points $(x,y)$ with $2 \leq x \leq y.$ The vast majority will turn out to be isolated points (for example those with $x$ even) so one might also consider generating paths as about to be defined and adding vertices as they arise.

From each point $(x,x),$ start a path $(x,x)=(x,f^0(x)),(x,f(x)),(x,f^2(x)),\cdots\ $ However stop at $(x,y)=(x,f^k(x))$ if it turns out that $f(y)=f^{k+1}(x) \lt x.$

Then this graph $H$ has an infinite path exactly if the conjecture is false. To get $G,$ add four vertices $a,b,c,d$ with edges $(a,b),(b,c),(c,d)$ and also add an edge from $d$ to each $(x,x).$ Then there is an infinite path in $G$ using $a,b,c,d$ exactly if $H$ has an infinite path.

In $G$ every vertex has degree $0,1$ or $2$ except that $d$ has infinite degree. There might be an easy variation which has all vertices of bounded (or at least finite) degree, however I could imagine that there isn't one.

Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104