state = {1, 2, 3};
MakeNext[state_List] := Module[{i = First[state], done = False, out},
  While[! done,
   If[FreeQ[state, i],
    If[GCD[Last[state], i] == 1,
     If[GCD[state[[-2]], i] > 1,
      out = Append[state, i];
      done = True;
      ]
     ]
    ];
   i++;
   ];
  out
  ]
Nest[MakeNext, state, 30 - 3]
ListPlot[%]