We show lower bounds of Ω(E/V Sort(V)) for the I/O-complexity of graph theoretic problems like connected components, biconnected components, and minimum spanning trees, where E and V are the number of edges and vertices in the input graph, respectively. We also present a deterministic O(E/V Sort(V)·max(1, log log VBD/E)) algorithm for the problem of graph connectivity, where B and D denote respectively the block size and number of disks. Our algorithm includes a breadth first search; this maybe of independent interest.