A couple notes here...
First, plotting a graph object creates a GraphPlot object, not a line, so it can't be used (out of the box) with animatedline. But you can get the same animated effect by looping like you've done in your example (it could be more efficient to update properties of the GraphPlot rather than redraw each time, but in this particular example the extra work isn't really worth it).
Second, if you don't specify the x/y coordinates of your graph nodes, the graph command chooses them based on certain properties of the graph. And those default x/y coordinates will change depending on the edges. Assuming you don't want that, you need to manually set the coordinates.
Finally, be careful how you're building your graphs. You want to preserve all the nodes, not just the ones with edges, I presume.
s = [1 2 3];
t = [2 3 4];
nnode = max([s t]);
x = ones(1,nnode);
y = 1:nnode;
g = graph(s,t);
axis([.5,3.5,-2,14]);
hold on;
for ii=1:length(s)
gplt = g;
gplt = rmedge(gplt, s(ii+1:end), t(ii+1:end));
if ii>1
delete(p);
end
p = plot(gplt, 'xdata', x, 'ydata', y, 'nodecolor', 'k', 'edgecolor', 'b');
drawnow
pause(1);
end
