I believe there are multiple solutions to each graph walk. For example the 999 run above returned 3 unique solutions. For the first 888 items, the graphs walks are the same, but from there on, there are slightly different cycles in the 3 found solutions.

Here are the position numbers and the values for the last 122 steps for each of the 3 solutions.

Code:

888 58 89 89

889 111 107 107

890 85 118 118

891 84 138 138

892 112 58 58

893 113 111 111

894 83 85 85

895 142 84 84

896 114 112 112

897 82 113 113

898 62 83 83

899 107 142 142

900 118 114 114

901 138 82 82

906 89 64 64

907 136 105 105

909 105 136 136

910 91 60 60

933 64 45 45

934 57 76 76

935 43 93 93

936 78 51 51

937 66 70 70

938 55 74 74

939 45 95 95

940 76 49 49

941 93 72 72

942 51 97 97

943 70 47 47

944 74 53 53

945 95 91 91

946 49 78 78

947 72 66 66

948 97 55 55

949 47 26 26

950 53 23 23

951 28 98 98

952 21 46 46

953 60 18 18

954 61 63 63

955 39 37 37

956 42 27 27

958 27 59 59

959 37 62 62

960 63 38 38

961 18 43 43

962 46 57 57

963 98 7 7

964 23 42 42

965 41 39 39

966 59 61 61

967 5 20 20

968 20 29 29

969 29 52 52

970 52 48 48

971 48 33 33

972 33 16 16

973 16 9 9

974 9 40 40

975 40 41 41

976 24 8 8

977 25 28 28

978 11 21 21

979 38 4 4

980 26 32 32

981 10 17 17

982 15 19 19

983 34 30 30

984 30 34 6

985 19 2 10

986 6 14 15

987 3 35 34

988 13 1 2

989 12 15 14

990 4 10 35

991 32 6 1

992 17 3 3

993 8 13 13

994 1 12 12

995 35 24 24

996 14 25 25

997 2 11 11

998 7 5 5

Edit to add:

Note- part of the multiple solutions has to do with "skeleton key" cycles like (6,19,30) that can appear in any order together. Mathematically these are the solutions occur when all permutations of a given numbers are subsets of the 3-node graph.

On the N=1000 graph there are only 828 such wonders (*6 if you include the permutations) out of 300300 valid combinations of 3 nodes. Each of these strings is an opportunity to create a new cycle in the graph.

Since the smallest pair of these is: (6, 19, 30) and (5, 20, 44),

If at least one solution exists for N>=44, there could be multiple solutions, since any solution could contain a pair of these special strings (one to depart the main thread and the other to come back).

A more thorough proof would prove that there are no isolated parts of the a particular graph (i.e. closed cycle), and that it contained one of these "skeleton keys".

Here are the most frequent nodes in the N=1000 graph super nodes with their associated counts:

Code:

[(2, 15),

(8, 13),

(20, 10),

(30, 10),

(32, 10),

(38, 10),

(44, 10),

(92, 10),

(12, 9),

(14, 9),

(18, 9),

(42, 9),

(48, 9),

(58, 9),

(68, 9),

(78, 9),

(80, 9),

(132, 9),

(194, 9),

(248, 9)]

an interesting pattern..