Which graphs allow infinite nonrepetitive walks? (Q2639070): Difference between revisions

An infinite walk in a graph G is an infinite sequence of vertices \(W=a_ 1a_ 2...a_ n..\). such that for each i, \(a_ ia_{i+1}\) is an edge of G. The walk W is nonrepetitive if W cannot be expressed as the concatenation of walks \(W_ 1W_ 2W_ 2W_ 3\) where the duplicated walk \(W_ 2\) is not trivial. It is shown that all connected graphs, except for paths with 4 or less vertices, have nonrepetitive infinite walks. This is equivalent to showing that a graph G has a nonrepetitive infinite walk if and only if G has a minor isomorphic to \(P_ 5\), \(C_ 3\), or \(K_{1,3}\).