  What is the chance that among a group of $n$ friends, there are $s$ friends
all of whom have the same birthday? This is the celebrated birthday problem
which can be formulated as the existence of a monochromatic $s$-clique $K_s$
($s$-matching birthdays) in the complete graph $K_n$, where every vertex of
$K_n$ is uniformly colored with $365$ colors (corresponding to birthdays). More
generally, for a general connected graph $H$, let $T(H, G_n)$ be the number of
monochromatic copies of $H$ in a uniformly random coloring of the vertices of
the graph $G_n$ with $c_n$ colors. In this paper we show that $T(H, G_n)$
converges to $\mathrm{Pois}(\lambda)$ whenever $\mathbb E T(H, G_n) \rightarrow
\lambda$ and $\mathrm{Var} T(H, G_n) \rightarrow \lambda$, that is, the
asymptotic Poisson distribution of $T(H, G_n)$ is determined just by the
convergence of its mean and variance. Moreover, this condition is necessary if
and only if $H$ is a star-graph. In fact, the second-moment phenomenon is a
consequence of a more general theorem about the convergence of $T(H,G_n)$ to a
finite linear combination of independent Poisson random variables. As an
application, we derive the limiting distribution of $T(H, G_n)$, when $G_n\sim
G(n, p)$ is the Erd\H os-R\'enyi random graph. Multiple phase-transitions
emerge as $p$ varies from 0 to 1, depending on whether the graph $H$ is
balanced or unbalanced.
