  We study the design of small cost temporally connected graphs, under various
constraints. We mainly consider undirected graphs of $n$ vertices, where each
edge has an associated set of discrete availability instances (labels). A
journey from vertex $u$ to vertex $v$ is a path from $u$ to $v$ where
successive path edges have strictly increasing labels. A graph is temporally
connected iff there is a $(u,v)$-journey for any pair of vertices $u,v,~u\not=
v$. We first give a simple polynomial-time algorithm to check whether a given
temporal graph is temporally connected. We then consider the case in which a
designer of temporal graphs can \emph{freely choose} availability instances for
all edges and aims for temporal connectivity with very small \emph{cost}; the
cost is the total number of availability instances used. We achieve this via a
simple polynomial-time procedure which derives designs of cost linear in $n$.
We also show that the above procedure is (almost) optimal when the underlying
graph is a tree, by proving a lower bound on the cost for any tree. However,
there are pragmatic cases where one is not free to design a temporally
connected graph anew, but is instead \emph{given} a temporal graph design with
the claim that it is temporally connected, and wishes to make it more
cost-efficient by removing labels without destroying temporal connectivity
(redundant labels). Our main technical result is that computing the maximum
number of redundant labels is APX-hard, i.e., there is no PTAS unless $P=NP$.
On the positive side, we show that in dense graphs with random edge
availabilities, there is asymptotically almost surely a very large number of
redundant labels. A temporal design may, however, be \emph{minimal}, i.e., no
redundant labels exist. We show the existence of minimal temporal designs with
at least $n \log{n}$ labels.
