Let $G$ be a graph with $n$ vertices and $m$ edges. What is the tightest upper bound on the running time of Depth First Search on $G$, when $G$ is represented as an adjacency matrix?

When a graph $G$ with $n$ vertices and $m$ edges is represented using an adjacency matrix:

1. DFS visits every vertex at most once.

2. To find all neighbors (adjacent vertices) of any vertex $u$, DFS must scan the entire row corresponding to $u$ in the $n \times n$ adjacency matrix, which takes $\Theta(n)$ time per vertex.

3. Since there are $n$ vertices, the total time required to inspect all adjacent vertices is:

   $$\sum_{u \in V} \Theta(n) = n \times \Theta(n) = \Theta(n^2)$$

Hence, the tightest bound on the running time of DFS using an adjacency matrix representation is $\Theta(n^2)$, making (C) the correct option.