# Discrete Mathematics

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

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)}