**1. A graph G is called a ….. if it is a connected acyclic graph**

a. Cyclic graph

b. Regular graph

c. Tree

d. Not a graph

**2. What is the probability of choosing correctly an unknown integer between 0 and 9 with 3 chances ?**

a. 963/1000

b. 966/1000

c. 968/1000

d. 969/1000

**3. In an undirected graph the number of nodes with odd degree must be**

a. Zero

b. Odd

c. Prime

d. Even

**4. A graph is a collection of**

a. Row and columns

b. Vertices and edges

c. Equations

d. None of these

**5. The relation { (1,2), (1,3), (3,1), (1,1), (3,3), (3,2), (1,4), (4,2), (3,4)} is**

a. Reflexive

b. Transitive

c. Symmetric

d. Asymmetric

**6. An undirected graph possesses an eulerian circuit if and only if it is connected and its vertices are**

a. all of even degree

b. all of odd degree

c. of any degree

d. even in number

**7. How many relations are there on a set with n elements that are symmetric and a set with n elements that are reflexive and symmetric ?**

a. 2n(n+1)/2 and 2n.3n(n–1)/2

b. 3n(n–1)/2 and 2n(n–1)

c. 2n(n+1)/2 and 3n(n–1)/2

d. 2n(n+1)/2 and 2n(n–1)/2

**8. The number of colours required to properly colour the vertices of every planer graph is**

a. 2

b. 3

c. 4

d. 5

**9. In how many ways can a president and vice president be chosen from a set of 30 candidates?**

a. 820

b. 850

c. 880

d. 870

**10. Consider an undirected random graph of eight vertices. The probability that there is an edge between a pair of vertices is ½. What is the expected number of unordered cycles of length three?**

a. 44409

b. 1

c. 7

d. 8

**11. In a graph if e=(u, v) means**

a. u is adjacent to v but v is not adjacent to u

b. e begins at u and ends at v

c. u is processor and v is successor

d. both b and c

**12. A minimal spanning tree of a graph G is**

a. A spanning sub graph

b. A tree

c. Minimum weights

d. All of above

**13. The number of leaf nodes in a complete binary tree of depth d is**

a. 2d

b. 2d–1+1

c. 2d+1+1

d. 2d+1

**14. A partial ordered relation is transitive, reflexive and**

a. Antisymmetric

b. Bisymmetric

c. Anti reflexive.

d. Asymmetric

**15. In a graph if e=[u, v], Then u and v are called**

a. Endpoints of e

b. Adjacent nodes

c. Neighbors

d. All of above

**16. In how many ways can a hungry student choose 3 toppings for his prize from a list of 10 delicious possibilities?**

a. 100

b. 120

c. 110

d. 150

**17. A graph with n vertices will definitely have a parallel edge or self loop if the total number of edges are**

a. greater than n–1

b. less than n(n–1)

c. greater than n(n–1)/2

d. less than n2/2

**18. A vertex of a graph is called even or odd depending upon**

a. Total number of edges in a graph is even or odd

b. Total number of vertices in a graph is even or odd

c. Its degree is even or odd

d. None of these

**19. In any undirected graph the sum of degrees of all the nodes**

a. Must be even

b. Are twice the number of edges

c. Must be odd

d. Need not be even

**20. The expression a+a c is equivalent to**

a. a

b. a+c

c. c

d. 1

**21. A graph with one vertex and no edges is**

a. multigraph

b. digraph

c. isolated graph

d. trivial graph

**22. Length of the walk of a graph is**

a. The number of vertices in walk W

b. The number of edges in walk W

c. Total number of edges in a graph

d. Total number of vertices in a graph

**23. A graph with no edges is known as empty graph. Empty graph is also known as**

a. Trivial graph

b. Regular graph

c. Bipartite graph

d. None of these

**24. Choose the most appropriate definition of plane graph**

a. A graph drawn in a plane in such a way that any pair of edges meet only at their end vertices

b. A graph drawn in a plane in such a way that if the vertex set of graph can be partitioned into two non – empty disjoint subset X and Y in such a way that each edge of G has one end in X and one end in Y

c. A simple graph which is Isomorphic to Hamiltonian graph

d. None of these

**25. A continuous non intersecting curve in the plane whose origin and terminus coincide**

a. Planer

b. Jordan

c. Hamiltonian

d. All of these

**26. A graph with n vertices will definitely have a parallel edge or self loop of the total number of edges are**

a. more than n

b. more than n+1

c. more than (n+1)/2

d. more than n(n-1)/2

**27. A debating team consists of 3 boys and 2 girls. Find the number of ways they can sit in a row?**

a. 120

b. 24

c. 720

d. 12

**28. Which one of the following statements is incorrect ?**

a. The number of regions corresponds to the cyclomatic complexity.

b. Cyclometric complexity for a flow graph G is V(G) = N–E+2, where E is the number of edges and N is the number of nodes in the flow graph.

c. Cyclometric complexity for a flow graph G is V(G) = E–N+2, where E is the number of edges & N is the number of nodes in the flow graph.

d. Cyclometric complexity for a flow graph G is V(G) = P + 1, where P is the number of predicate nodes contained in the flow graph G.

**29. The maximum degree of any vertex in a simple graph with n vertices is**

a. n–1

b. n+1

c. 2n–1

d. n

**30. The complete graph with four vertices has k edges where k is**

a. 3

b. 4

c. 5

d. 6

**31. Consider a weighted undirected graph with positive edge weights and let (u, v) be an edge in the graph. It is known that the shortest path from source vertex s to u has weight 53 and shortest path from s to v has weight 65. Which statement is always true**

a. Weight (u, v) <= 12

b. Weight (u, v) = 12

c. Weight (u, v) >= 12

d. Weight (u, v) > 12

**32. How many onto (or surjective) functions are there from an n-element (n => 2) set to a 2-element set?**

a. 2n

b. 2n – 1

c. 2n – 2

d. 2(2n – 2)

**33. Suppose v is an isolated vertex in a graph, then the degree of v is**

a. 0

b. 1

c. 2

d. 3

**34. The number of nodes in a complete binary tree of height h (with roots at level 0) is equal to**

a. 20 + 21 + ….. 2h

b. 20 + 21 + ….. 2h-1

c. 20 + 21 + ….. 2h+1

d. 21 + ….. 2h+1

**35. Hasse diagram are drawn**

a. Partially ordered sets

b. Lattices

c. Boolean algebra

d. None of these

**36. In how many ways can 5 balls be chosen so that 2 are red and 3 are black**

a. 910

b. 990

c. 970

d. 960

**37. Circle has ____________**

a. No vertices

b. Only 1 vertex

c. 8 vertices

d. None of these

**38. How many different words can be formed out of the letters of the word VARANASI?**

a. 64

b. 120

c. 40320

d. 720

**39. A graph is tree if and only if**

a. Is planar

b. Contains a circuit

c. Is minimally

d. Is completely connected

**40. If B is a Boolean Algebra, then which of the following is true**

a. B is a finite but not complemented lattice

b. B is a finite, complemented and distributive lattice

c. B is a finite, distributive but not complemented lattice

d. B is not distributive lattice

**41. The number of distinguishable permutations of the letters in the word BANANA are,**

a. 60

b. 36

c. 20

d. 10

**42. If R is a relation “Less Than” from A = {1,2,3,4} to B = {1,3,5} then RoR-1 is**

a. {(3,3), (3,4), (3,5)}

b. {(3,1), (5,1), (3,2), (5,2), (5,3), (5,4)}

c. {(3,3), (3,5), (5,3), (5,5)}

d. {(1,3), (1,5), (2,3), (2,5), (3,5), (4,5)}

**Answer Key:**

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |

c | a | d | b | b | a | d | d | d | c |

11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |

d | d | a | a | d | b | a | c | b | b |

21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |

d | b | a | a | b | d | a | b | a | d |

31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 |

c | c | a | a | a | b | a | d | c | b |

41 | 42 | ||||||||

a | c |