Question

Given a graph G, F is a spanning tree of G, if
(i) F is subgraph of G containing all the nodes of G
(ii) F is an ordered forest containing tree $T_1,T_2,......$ Tn.
(iii) Ti contain all the nodes that are reachable in G from the root Ti and are not contained in Ti for some j<i of these.

• A. (i) and (ii)
• B. (ii) and (iii)
• C. (i) and (iii)
• D. (i), (ii) and (iii)

Answer 1

The correct option is D (i), (ii) and (iii)

A graph G, F is a spanning tree of G, if
(i) F is subgraph of G containing all the nodes of G.
(ii) F is an ordered forest containing tree T1,T2,...... Tn.
(iii) Ti contain all the nodes that are reachable in G from the root Ti and are not contained in Ti for some j<i of these.

All the options are true.

Spanning tree:-

A spanning tree is a subset of graph G, which has all the vertices covered with minimum possible number of edges. Hence, a spanning tree does not have cycles and it cannot be disconnected.

A subgraph S of a graph G is a graph whose set of vertices and set of edges are all subsets of G. A spanning subgraph is a subgraph that contains all the vertices of the original graph.