51. Determine the longest string which is described by the given Directed Acyclic Word Graph.
a. BATS
b. BOATS
c. BOT
d. None of the mentioned
Answer: (a).BATS

52. Which of the following statements for a simple graph is correct?
a. Every path is a trail
b. Every trail is a path
c. Every trail is a path as well as every path is a trail
d. None of the mentioned
Answer: (a).Every path is a trail

53. What is the number of edges present in a complete graph having n vertices?
a. (n*(n+1))/2
b. (n*(n-1))/2
c. n
d. Information given is insufficient
Answer: (b).(n*(n-1))/2

54. In a simple graph, the number of edges is equal to twice the sum of the degrees of the vertices.
a. True
b. False
c. May be
d. Can't say
Answer: (b).False

55. A connected planar graph having 6 vertices, 7 edges contains _____________ regions.
a. 15
b. 3
c. 1
d. 11
Answer: (b).3

56. If a simple graph G, contains n vertices and m edges, the number of edges in the Graph G'(Complement of G) is ___________
a. (n*n-n-2*m)/2
b. (n*n+n+2*m)/2
c. (n*n-n-2*m)/2
d. (n*n-n+2*m)/2
Answer: (c).(n*n-n-2*m)/2

57. Which of the following properties does a simple graph not hold?
a. Must be connected
b. Must be unweighted
c. Must have no loops or multiple edges
d. All of the mentioned
Answer: (a).Must be connected

58. What is the maximum number of edges in a bipartite graph having 10 vertices?
a. 24
b. 21
c. 25
d. 16
Answer: (c).25

59. Which of the following is true?
a. A graph may contain no edges and many vertices
b. A graph may contain many edges and no vertices
c. A graph may contain no edges and no vertices
d. None of the mentioned
Answer: (b).A graph may contain many edges and no vertices

60. For a given graph G having v vertices and e edges which is connected and has no cycles, which of the following statements is true?
a. v=e
b. v = e+1
c. v + 1 = e
d. None of the mentioned
Answer: (b).v = e+1

Page 6 of 17