Let $G(V, E)$ be an undirected and unweighted graph with 100 vertices. Let $d(u, v)$ denote the number of edges in a shortest path between vertices $u$ and $v$ in $V$. Let the maximum value of $d(u, v)$, $u, v \in V$ such that $u \neq v$, be 30. Let $T$ be any breadth-first-search tree of $G$. Which ONE of the given options is CORRECT for every such graph $G$?

The diameter of the graph $G$ is given as:

Let $r$ be the root vertex chosen to start the Breadth-First Search (BFS). In a BFS tree $T$ rooted at $r$, the depth (level) of any vertex $v$ corresponds to the shortest path distance from $r$ to $v$, i.e., $d(r, v)$.

The height of the BFS tree $T$ is the maximum distance from the root $r$ to any vertex in the graph:

By the triangle inequality for shortest path distances in an undirected graph, for any pair of vertices $u, v \in V$:

Since $d(u, r) \le h(T)$ and $d(r, v) \le h(T)$, we have:

Taking the maximum over all pairs $(u, v)$:

Depending on the choice of the root $r$, the height $h(T)$ can range from $\lceil 30/2 \rceil = 15$ (if $r$ is a central vertex) up to $30$ (if $r$ is an eccentric peripheral vertex). Thus, the height of $T$ is always at least $15$.

Hence, option C is correct.