Let me check that I understand you correctly.

Let $Y(t)$ be the $n+1$-dimensional vector $Y(t) = \otimes_{i=0}^n Y^t_i$ where $Y^t_i$ represents the number of verticies with degree $i$ at time $t$. When time increases by $1$, add an edge at random.

So, $Y(0) = (n,0,0,\ldots,0)$, $Y(1) = (n-2,2,0,\ldots,0)$,

$Y(2) = (n-4,4,0,0,\ldots,0)$ if the new edge is not adjacent to the old edge, or
$Y(2) = (n-3,2,1,0,\ldots,0)$ if the new edge is adjacent to the old edge.

At time $t$, the new edge is chosen at random by choosing one vertex of degree $i$ with probability $Y^t_i/(n - Y^t_n)$ and another of degree $j$ with probability $Y^t_j/(n - Y^t_n - 1)$ if $j\neq i$ and probability $(Y^t_j-1)/(n - Y^t_n-1)$ if $j=i$.

Assuming $j\neq i$ (a simple adjustment is necessary for the $i=j$ case), the probability moving from $Y(t)$ to $Y(t+1)$ where $Y^{t+1}_k = Y^t_k - 1$ and $Y^{t+1}_k = Y^t_k + 1$ for $k= i,j$ and $Y^{t+1}_k = Y^t_k$ for $k \neq i,j$ is therefore
$$\frac{Y^t_i Y^t_j}{2(n - Y^t_n)(n - Y^t_n-1)} $$
Which only depends on the present state, and is independent of the history of the previous $t-1$ steps. Hence it is a Markov chain.