This creates an Eulerian random graph with n nodes. 
Then it looks for an Eulerian tour.

How to use this notebook

First run Routines. Then open Graph creation and create a graph. This graph is eulerian by construction. Running the Euler tour search section the Euler tour is computed

Routines

Off[General::spell1]

lookfornode:=Block[{},
    pointer=1;
    While[(pointer<=n) &&
    (!adj[[cn,pointer]] || marked[[cn,pointer]]),
    pointer++];
    If[pointer<=n,
       newnode=pointer;
       nomorenodes=False;,
       nomorenodes=True;
       ]
       
];

creategraph:=Block[{},
d=5;
prob=d/(n-1);
arcs={};
parity=Table[True,{n}];
degree=Table[0,{n}];
Do[If[Random[]<prob,
      AppendTo[arcs,{i,j}];
      parity[[i]]=!parity[[i]];
      degree[[i]]++;degree[[j]]++;
      parity[[j]]=!parity[[j]];
      ],
      {i,1,n-1},{j,i+1,n}];
oddnodes={};
Do[If[parity[[i]],,AppendTo[oddnodes,i]],{i,n}];
Do[index=Random[Integer,{1,Length[oddnodes]}];
k1=oddnodes[[index]];
oddnodes=Drop[oddnodes,{index,index}];
index=Random[Integer,{1,Length[oddnodes]}];
k2=oddnodes[[index]];
oddnodes=Drop[oddnodes,{index,index}];
If[k1>k2,kk1=k1;k1=k2;k2=kk1];
If[MemberQ[arcs,{k1,k2}]
   ,t=Position[arcs,{k1,k2}][[1,1]];
    arcs=Drop[arcs,{t,t}];
    degree[[k1]]--;degree[[k2]]--;
   ,
    AppendTo[arcs,{k1,k2}];
    degree[[k1]]++;degree[[k2]]++;
    ],
{Length[oddnodes]/2}];
adj=Table[False,{n},{n}];
Do[k1=arcs[[k,1]];
   k2=arcs[[k,2]];
   adj[[k1,k2]]=True;
   adj[[k2,k1]]=True
   ,{k,Length[arcs]}]
   ]

Graph creation

n=12; (* n is the numer of nodes *)
x=Table[5 {Sin[2 N[Pi]/n i],Cos[2 N[Pi]/n i]},{i,0,n-1}];

creategraph;

list of generated arcs

arcs

bbb=Graphics[Table[
      Line[{x[[arcs[[i,1]]]],x[[arcs[[i,2]]]]}],
    {i,Length[arcs]}]];

aaa=Graphics[{PointSize[0.02],Table[{Point[x[[i]]],
      Text[ToString[i],x[[i]],0.5{-x[[i,1]],-x[[i,2]]}]},{i,Length[x]}]}];
      Show[aaa,bbb,AspectRatio->Automatic
      ];

Eulerian tour search

marked=Table[False,{n},{n}];

path={1};
cn=1;
stop=False;
counter=0;
While[ !stop,
     lookfornode;
     If[nomorenodes,
            stop=True;
           ,marked[[cn,newnode]]=True;
            marked[[newnode,cn]]=True;
            cn=newnode;
            degree[[cn]]=degree[[cn]]-2;
            AppendTo[path,cn];
            Print[path]
        ]
       ];
   
Eulerpath=path;
end=False;
While[!end,
kk=1;While[(kk<=n) && (degree[[kk]]==0), kk++];
startnode=kk;
If[startnode>n,end=True
,
insert=Position[Eulerpath,kk][[1,1]];
path={startnode};
cn=startnode;
stop=False;
counter=0;
While[ !stop,
     lookfornode;
     If[nomorenodes,
            stop=True;
           ,marked[[cn,newnode]]=True;
            marked[[newnode,cn]]=True;
            cn=newnode;
            degree[[cn]]=degree[[cn]]-2;
            AppendTo[path,cn];
            Print[path]
        ]
       ];
       Eulerpath[[insert]]=path;
       Eulerpath=Flatten[Eulerpath];
       ]
       ];
       Eulerpath

Animation

It demands a lot of memory !

Do[ccc=Graphics[{RGBColor[1,0,0],Thickness[0.010],
     Table[Line[{x[[Eulerpath[[i]]]],x[[Eulerpath[[i+1]]]]}],
    {i,j}]}];
    Show[aaa,bbb,ccc,AspectRatio->Automatic]
    ,{j,Length[Eulerpath]-1}]