I'll show you the adjacency matrix. You store a D array where M[i][j] = 1 if there is an edge from vertex to vertex , and otherwise. In an undirected graph the matrix is symmetric because connects to and connects to .
Checking whether edge exists takes time because you read M[u][v]. The cost is space. You store entries, so it uses space even when the graph is sparse. If you are memory bound, you will feel this immediately.