  A well known result of Erd\H{o}s and R\'enyi states that if $p = \frac{c \log
n}{n}$ and $G$ is a random graph constructed from $G(n,p)$, $G$ is a.a.s.
disconnected when $c < 1$, and $G$ is a.a.s. connected when $c > 1$. When $c >
1$, we may equivalently say that $G$ a.a.s. contains a spanning tree. We find
analogous thresholds in the setting of random edge-colored graphs.
Specifically, we consider a family $\mathcal G$ of $n-1$ graphs on a common set
$X$ of $n$ vertices, each of a different color, and each randomly chosen from
$G(n,p)$, with $p = \frac{c \log n}{n^2}$. We show that when $c > 2$, there
a.a.s. exists a spanning tree on $X$ using exactly one edge of each color, and
we show that such a spanning tree a.a.s. does not exist when $c < 2$.
