31. For an undirected graph G with n vertices and e edges, the sum of the degrees of each vertex is a. ne b. 2n c. 2e d. e^n
 Answer: (c).2e

 32. A complete graph can have ............... a. n^2 spanning trees b. n^(n-2) spanning trees c. n^(n+1) spanning trees d. n^n spanning trees
 Answer: (b). n^(n-2) spanning trees

 33. Graph traversal is different from a tree traversal, because: a. trees are not connected b. graphs may have loops c. trees have root d. None of these
 Answer: (c).trees have root

 34. The number of edges in a simple, n-vertex, complete graph is a. n*(n-2) b. n*(n-1) c. n*(n-1)/2 d. n*(n-1)*(n-2)
 Answer: (c).n*(n-1)/2

 35. Graphs are represented using ............ a. Adjacency tree b. Adjacency linked list c. Adjacency graph d. Adjacency queue
 Answer: (b).Adjacency linked list

 36. The spanning tree of connected graph with 10 vertices contains .............. a. 9 edges b. 11 edges c. 10 edges d. 9 vertices
 Answer: (a).9 edges

 37. If locality is a concern, you can use ................ to traverse the graph. a. Breadth First Search b. Depth First Search c. Either BFS or DFS d. None of these
 Answer: (b).Depth First Search

 38. Which of the following algorithms solves the all-pair shortest path problem? a. Floyd's algorithm b. Prim's algorithm c. Dijkstra's algorithm d. Warshall's algorithm
 Answer: (a).Floyd's algorithm

 39. The minimum number of colors needed to color a graph having n (>3) vertices and 2 edges is a. 1 b. 2 c. 3 d. 4
 Answer: (b).2

 40. Which of the following is useful in traversing a given graph by breadth first search? a. set b. List c. stacks d. Queue
 Answer: (d).Queue

Page 4 of 17