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