Statement-1: FALSE: Root of T can never be an articulation point in G.
Statement-2:
Example-1:
If u is an articulation point in G such that x is an ancestor of u in T and y is a descendent of u in T, then all paths from x to y in G must pass through u.




Here 2 and 6 are articulation points. If you consider node-1 ancestor and node-3 descendent, then without passing through from node -2, there exists a path from one node to another node.
Path from node-1 to node-3 If you consider node-5 ancestor and node-4 descendent, then without passing through from node-6, there exists a path from one node to another node.
Path from node-4 to node-5
The given statement is not TRUE for all cases. So, the given statement is FALSE.
Statement-3: FALSE: Leafs of a DFS-tree are never articulation points.
Statement-4: TRUE: The root of a DFS-tree is an articulation point if and only if it has at least two children.


Node 2 is an AP because any node from the first subtree (1, 2) is connected to any node from the second subtree (4, 5, 6, 7, 8) by a path that includes node 2. If node 2 is removed, the 2 subtrees are disconnected.

In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible.

A={0,1,2} → BFS

The BFS traverse through level by level. 

DFS:

B={0,1,3} 

B={0,1,4}

B={0,2,6}

B={0,2,5}

The DFS starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.

|A-B| = 1

Note: The cardinality of set A-B is 1. 

(A) Not True: Back edges are still possible in this scenario, as explained before. (B) Not True: While the BFS aspect reduces the likelihood of cross-edges, it's not guaranteed. Imagine a graph with a cycle that connects back to an earlier explored level. Such a cycle would create a cross-edge in G relative to T. (C) True: In a BFS tree, all vertices at a level are explored before moving to the next level. This ensures that for any two connected vertices in G: If they are in the same level of T, there cannot be a forward edge because BFS explores neighbors at a level before moving deeper (they would be explored in the opposite order if it were a forward edge). If one vertex is an ancestor of the other in T, it cannot be a forward edge by definition (a forward edge points from a vertex to its descendant). Therefore, since T is both a DFS spanning tree and a BFS tree rooted at v, all edges in T must be either back edges (pointing to an ancestor) or edges that explore neighbors at the same level. This eliminates the possibility of forward edges in G with respect to T.