  We consider temporal graphs with discrete time labels and investigate the
size and the approximability of minimum temporally connected spanning
subgraphs. We present a family of minimally connected temporal graphs with $n$
vertices and $\Omega(n^2)$ edges, thus resolving an open question of (Kempe,
Kleinberg, Kumar, JCSS 64, 2002) about the existence of sparse temporal
connectivity certificates. Next, we consider the problem of computing a minimum
weight subset of temporal edges that preserve connectivity of a given temporal
graph either from a given vertex r (r-MTC problem) or among all vertex pairs
(MTC problem). We show that the approximability of r-MTC is closely related to
the approximability of Directed Steiner Tree and that r-MTC can be solved in
polynomial time if the underlying graph has bounded treewidth. We also show
that the best approximation ratio for MTC is at least $O(2^{\log^{1-\epsilon}
n})$ and at most $O(\min\{n^{1+\epsilon}, (\Delta M)^{2/3+\epsilon}\})$, for
any constant $\epsilon > 0$, where $M$ is the number of temporal edges and
$\Delta$ is the maximum degree of the underlying graph. Furthermore, we prove
that the unweighted version of MTC is APX-hard and that MTC is efficiently
solvable in trees and $2$-approximable in cycles.
