  In this paper we study graph problems in dynamic streaming model, where the
input is defined by a sequence of edge insertions and deletions. As many
natural problems require $\Omega(n)$ space, where $n$ is the number of
vertices, existing works mainly focused on designing $\tilde{O}(n)$ space
algorithms. Although sublinear in the number of edges for dense graphs, it
could still be too large for many applications (e.g. $n$ is huge or the graph
is sparse). In this work, we give single-pass algorithms beating this space
barrier for two classes of problems.
  We present $o(n)$ space algorithms for estimating the number of connected
components with additive error $\varepsilon n$ and
$(1+\varepsilon)$-approximating the weight of minimum spanning tree, for any
small constant $\varepsilon>0$. The latter improves previous $\tilde{O}(n)$
space algorithm given by Ahn et al. (SODA 2012) for connected graphs with
bounded edge weights.
  We initiate the study of approximate graph property testing in the dynamic
streaming model, where we want to distinguish graphs satisfying the property
from graphs that are $\varepsilon$-far from having the property. We consider
the problem of testing $k$-edge connectivity, $k$-vertex connectivity,
cycle-freeness and bipartiteness (of planar graphs), for which, we provide
algorithms using roughly $\tilde{O}(n^{1-\varepsilon})$ space, which is $o(n)$
for any constant $\varepsilon$.
  To complement our algorithms, we present $\Omega(n^{1-O(\varepsilon)})$ space
lower bounds for these problems, which show that such a dependence on
$\varepsilon$ is necessary.
