  This paper presents a comprehensive study of algorithms for maintaining the
number of all connected four-vertex subgraphs in a dynamic graph. Specifically,
our algorithms maintain the number of paths of length three in deterministic
amortized $\mathcal{O}(m^\frac{1}{2})$ update time, and any other connected
four-vertex subgraph which is not a clique in deterministic amortized update
time $\mathcal{O}(m^\frac{2}{3})$. Queries can be answered in constant time. We
also study the query times for subgraphs containing an arbitrary edge that is
supplied only with the query as well as the case where only subgraphs
containing a vertex $s$ that is fixed beforehand are considered. For length-3
paths, paws, $4$-cycles, and diamonds our bounds match or are not far from
(conditional) lower bounds: Based on the OMv conjecture we show that any
dynamic algorithm that detects the existence of paws, diamonds, or $4$-cycles
or that counts length-$3$ paths takes update time $\Omega(m^{1/2-\delta})$.
  Additionally, for $4$-cliques and all connected induced subgraphs, we show a
lower bound of $\Omega(m^{1-\delta})$ for any small constant $\delta > 0$ for
the amortized update time, assuming the static combinatorial $4$-clique
conjecture holds. This shows that the $\mathcal{O}(m)$ algorithm by Eppstein at
al. for these subgraphs cannot be improved by a polynomial factor.
