1) is false . For eg consider the graph 1 <- 2 -> 3.
Case 1: If we start dfs from vertex 2 we will get single tree
. 1<- 2 -> 3
Case 2 : If we start dfs from 3, we will get 1 tree containing vertex 3. After doing dfs on vertex 3 we can choose either 1 or 2. Sippose we choose 2 . If we dfs from 2 we will get another tree containing 1 and 2
Tree 1: DFS(3) 3
Tree 2: DFS(2) 1 <- 2
So clearly number of DFS trees may vary if we start DFS from different vertices.
Claim 2 :G - Graph with n vertices and m edges. All its DFS forests will have same number of tree edges and same number of back edges. The above example is itself is a contradiction. To state more clearly Let the number of components in DFS forest be k. Let the number of nodes in ith component be ci. then the number of tree edges in the ith component is ci-1 (because it is a tree). So total number of tree edges is c1+c2...+ck . This sum will vary for each DFS forest because each DFS forest will have different number of component of different sizes.
