"Computing on data streams" clarification
The definition says that every edge that exists has to go from some $V_i$ to $V_{i+1}$.  It doesn't say that every possible edge from $V_i$ to $V_{i+1}$ has to be there.  For example, $V_1=\{a,b\}$, $V_2=\{c,d\}$ with edges $ac$ and $bd$ gives a disconnected graph.