A ''universal traversal sequence'' is a sequence of instructions comprising a graph traversal for any [[regular graph]] with a set number of vertices and for any starting vertex. A probabilistic proof was used by Aleliunas et al. to show that there exists a universal traversal sequence with number of instructions proportional to {{nowrap|''O''(''n''<sup>5</sup>)}} for any regular graph with ''n'' vertices.<ref>{{cite journalbook|last1=Aleliunas|first1=R.|last2=Karp|first2=R.|last3=Lipton|first3=R.|last4=Lovász|first4=L.|last5=Rackoff|first5=C. |title=20th Annual Symposium on Foundations of Computer Science (SFCS 1979) |chapter=Random walks, universal traversal sequences, and the complexity of maze problems|journal=20thAnnual Symposium on Foundations of Computer Science (SFCS 1979)|pages=218–223|date=1979|doi=10.1109/SFCS.1979.34|s2cid=18719861 }}</ref> The steps specified in the sequence are relative to the current node, not absolute. For example, if the current node is ''v''<sub>''j''</sub>, and ''v''<sub>''j''</sub> has ''d'' neighbors, then the traversal sequence will specify the next node to visit, ''v''<sub>''j''+1</sub>, as the ''i''<sup>th</sup> neighbor of ''v''<sub>''j''</sub>, where 1 ≤ ''i'' ≤ ''d''.
