We study set systems over the vertex set (or edge set) of some graph that are induced by special graph properties like clique, connectedness, path, star, tree, etc. We derive a variety of combinatorial and computational results on the VC (Vapnik-Chervonenkis) dimension of these set systems. For most of these set systems (e.g. for the systems induced by trees, connected sets, or paths), computing the VC-dimension is an NP-hard problem. Moreover, determining the VC-dimension for set systems induced by neighborhoods of single vertices is complete for the class LogNP. In contrast to these intractability results, we show that the VC-dimension for set systems induced by stars is computable in polynomial time. For set systems induced by paths or cycles, we determine the extremal graphs G with the minimum number of edges such that VC (G) k. Finally, we show a close relation between the VC-dimension of set systems induced by connected sets of vertices and the VC dimension of set systems induced by connected sets of edges; the argument is done via the line graph of the corresponding graph.