Which of the following statements regarding Breadth First Search (BFS) and Depth First Search (DFS) on an undirected simple graph G is/are TRUE?

The correct statements are:
1. Every non-tree edge of G with respect to a DFS tree is a forward/back edge.
2. If (u, v) is a non-tree edge of G with respect to a BFS tree, then the distances from the source vertex s to u and v in the BFS tree are within ±1 of each other.
3. Both BFS and DFS can be used to find the connected components of G.

Let us analyze each statement step-by-step to understand why they are true or false:

Statement 1: A DFS tree of G is a Shortest Path tree of G. (FALSE)
Depth First Search (DFS) explores as deep as possible along each branch before backtracking. It does not guarantee finding the shortest path (in terms of the number of edges) from the source to other vertices. In contrast, Breadth First Search (BFS) is specifically designed to find the shortest path tree in an unweighted graph. For example, in a cycle graph of three vertices A-B-C-A, starting DFS at A might yield the path A-B-C, making the distance from A to C equal to 2, whereas the shortest path is direct from A to C with a distance of 1.

Statement 2: Every non-tree edge of G with respect to a DFS tree is a forward/back edge. (TRUE)
In an undirected graph, when we perform a Depth First Search, the edges of the graph are classified into two categories: tree edges (edges in the DFS forest) and back edges (non-tree edges that connect a vertex to an ancestor in the DFS tree). Under undirected DFS, there are no cross edges or forward edges that are not ancestors/descendants. Since the graph is undirected, a back edge and a forward edge are structurally the same (just viewed from different endpoints), so every non-tree edge is a back edge (which can also be referred to as a forward/back edge). Thus, this statement is true.

Statement 3: If (u, v) is a non-tree edge of G with respect to a BFS tree, then the distances from the source vertex s to u and v in the BFS tree are within ±1 of each other. (TRUE)
In a Breadth First Search on an undirected graph, vertices are discovered in layers based on their shortest-path distance from the source vertex $s$. Let $d(s,x)$ denote the shortest distance from $s$ to $x$.
For any edge $(u,v)$ in an undirected graph $G$, the distance of the endpoints from the source can differ by at most 1. That is:
$\left|d\right(s,u)-d(s,v\left)\right|\le 1$
This inequality holds for all edges in the graph, whether they are tree edges or non-tree edges. Therefore, if $(u,v)$ is a non-tree edge, the distances from the source $s$ to $u$ and $v$ must satisfy:
$d(s,u)-d(s,v)\in \{-1,0,1\}$
which means the distances are within $\pm 1$ of each other. Hence, this statement is true.

Statement 4: Both BFS and DFS can be used to find the connected components of G. (TRUE)
A single execution of BFS or DFS starting from a vertex will visit all vertices in its connected component. By wrapping the search in a loop that iterates through all vertices and starts a new BFS or DFS traversal whenever an unvisited vertex is encountered, we can systematically discover and label all connected components of an undirected graph. Thus, both algorithms are widely used for this purpose, making this statement true.