21.  A connected graph T without any cycles is called ........ 
Answer: (a).free graph

22.  In a graph if E=(u,v) means ...... 
Answer: (d).both b and c

23.  Let G = (V, E) be any connected undirected edgeweighted graph. The weights of the edges in E are positive any distinct. Consider the following statements: I. Minimum Spanning Tree of G is always unique. II. Shortest path between any two vertices of G is always unique. Which of the above statements is/are necessarily true? 
Answer: (a).I only

24.  Let A be an adjacency matrix of a graph G. The ij th entry in the matrix Ak , gives 
Answer: (b).Shortest path of K edges from vertex Vi to vertex Vj.

25.  For an undirected graph with n vertices and e edges, the sum of the degree of each vertex is equal to 
Answer: (c).2e

26.  An undirected graph G with n vertices and e edges is represented by adjacency list. What is the time required to generate all the connected components? 
Answer: (c).O (e+n)

27.  A graph with n vertices will definitely have a parallel edge or self loop if the total number of edges are 
Answer: (d).more than n(n1)/2

28.  The maximum degree of any vertex in a simple graph with n vertices is 
Answer: (a).n–1

29.  The data structure required for Breadth First Traversal on a graph is 
Answer: (a).queue

30.  In Breadth First Search of Graph, which of the following data structure is used? 
Answer: (b).Queue
