Relationship between Las Vegas algorithms and deterministic algorithms
There is no contradiction here. A Las Vegas algorithm terminates in expected polynomial time, say $Q(n)$. Markov's inequality shows that for any given polynomial $R(n)$, it terminates in polynomial time $Q(n)R(n)$ with probability $1-1/R(n)$. The number of graphs on $n$ vertices, $k(n)$, is exponential in $n$, so the failure probability $1/R(n)$ is much larger than $1/k(n)$.

Another subtle point is uniformity. A deterministic algorithm needs to handle any input size, while your $A^\rho$ can only handle inputs of certain size. In general, a randomized algorithm can use an unbounded number of random bits. However, your argument can still be formulated in terms of non-uniform models such as circuits, and it is still wrong for the reason described above.