 Solution

Part (a) says that every partial embedding preserves every formula. By the characterization supplied in the question, each formula is therefore equivalent modulo $T_{\mathrm{rg}}$ to a quantifier-free formula. Hence the quantifier elimination for the random graph holds.