In this paper, we study the Eigenvalue Complementarity Problem (EiCP) when its matrix A belongs to the class S(G) = {A = [aij ] : aij = aji <> 0 iff ij in E}, where G = (V;E) is a connected graph. It is shown that if all non diagonal elements of A in S(G) are non positive, then A has a unique complementary eigenvalue, which is the smallest eigenvalue of A. In particular, zero is the unique complementary eigenvalue of the Laplacian and the normalized Laplacian matrices of a connected graph. The number c(G) of complementary eigenvalues of the adjacency matrix of a connected graph G is shown to be bounded above by the number b(G) of induced non isomorphic connected subgraphs of G. Furthermore, c(G) = b(G) if the Perron roots of the adjacency matrices of these subgraphs are all distinct. Finally, the maximum number of complementary eigenvalues for the adjacency matrices of graphs is shown to grow exponentially with the number of nodes.