DISCRETE MATHEMATICS MCQS

This comprehensive collection of Discrete Mathematics MCQs is specifically crafted to enhance understanding of the essential concepts and principles that form the foundation of discrete mathematics. Covering key topics such as set theory, graph theory, combinatorics, logic, and algorithms, these questions aim to reinforce both theoretical knowledge and practical application. Ideal for students pursuing mathematics, computer science, and related fields, as well as professionals preparing for certification exams, this set focuses on the critical elements that contribute to problem-solving and analytical thinking in discrete mathematics.

Who should practice Discrete Mathematics MCQs?

Students preparing for exams in discrete mathematics, computer science, and mathematics-related disciplines.
Professionals seeking to deepen their understanding of discrete mathematics for career advancement in fields such as software development and data analysis.
Candidates preparing for certification exams in computer science or mathematics.
Individuals looking to refresh their knowledge of discrete mathematical concepts and techniques.
Anyone interested in building a strong foundation in discrete mathematics to pursue further studies or a career in technology, research, or academia.

1. Which of the following is a basic concept of discrete mathematics?

a) Calculus
b) Linear algebra
c) Set theory
d) Differential equations

View Answer

2. In set theory, what does the symbol ∅ represent?

a) A non-empty set
b) The universal set
c) The empty set
d) A subset

View Answer

3. What is the result of the intersection of two disjoint sets?

a) The universal set
b) The empty set
c) The union of the sets
d) One of the sets

View Answer

4. Which of the following is not a property of equivalence relations?

a) Reflexivity
b) Symmetry
c) Transitivity
d) Antisymmetry

View Answer

5. In graph theory, what is a ‘path’?

a) A sequence of vertices connected by edges
b) A set of vertices without edges
c) A single edge connecting two vertices
d) A cycle of vertices

View Answer

6. What is a ‘bipartite graph’?

a) A graph with no cycles
b) A graph where vertices can be divided into two disjoint sets
c) A graph where all vertices are connected
d) A graph with exactly two edges

View Answer

7. In a directed graph, what is an ‘out-degree’ of a vertex?

a) The number of edges incident to the vertex
b) The number of edges leaving the vertex
c) The number of edges entering the vertex
d) The number of vertices adjacent to the vertex

View Answer

8. What is the principle of mathematical induction used for?

a) Proving inequalities
b) Finding the largest common divisor
c) Proving statements for all natural numbers
d) Calculating probabilities

View Answer

9. What does the ‘Pigeonhole Principle’ state?

a) There are more pigeonholes than pigeons
b) If more items are placed into fewer containers than items, at least one container must hold more than one item
c) All items will be evenly distributed among containers
d) Containers are always empty

View Answer

10. In Boolean algebra, what is the result of the expression A ∧ ¬A?

a) A
b) ¬A
c) 1
d) 0

View Answer

11. What is a ‘complement’ of a set A in set theory?

a) The set containing all elements not in A
b) The set containing only elements of A
c) The set containing elements that are common to A and another set
d) The set containing the union of A and another set

View Answer

12. Which of the following is a characteristic of a ‘complete graph’?

a) All vertices are connected to every other vertex
b) The graph contains no edges
c) The graph has exactly one vertex
d) The graph is bipartite

View Answer

13. What is the definition of a ‘tree’ in graph theory?

a) A connected graph with no cycles
b) A disconnected graph with cycles
c) A complete graph
d) A graph with exactly two vertices

View Answer

14. In a relation, what does ‘reflexivity’ mean?

a) Every element is related to itself
b) Every element is related to every other element
c) The relation is symmetric
d) The relation is transitive

View Answer

15. What is the chromatic number of a graph?

a) The number of edges in the graph
b) The minimum number of colors needed to color the vertices so that no two adjacent vertices share the same color
c) The number of vertices in the graph
d) The number of cycles in the graph

View Answer

16. Which algorithm is used to find the shortest path in a weighted graph?

a) Dijkstra’s algorithm
b) Kruskal’s algorithm
c) Prim’s algorithm
d) Bellman-Ford algorithm

View Answer

17. What is the ‘Eulerian path’ in graph theory?

a) A path that visits every edge exactly once
b) A path that visits every vertex exactly once
c) A cycle that visits every edge exactly once
d) A cycle that visits every vertex exactly once

View Answer

18. What is the ‘Hamiltonian cycle’?

a) A cycle that visits every vertex exactly once
b) A cycle that visits every edge exactly once
c) A path that visits every edge exactly once
d) A path that visits every vertex exactly once

View Answer

19. Which of the following is not a characteristic of a function?

a) Each element in the domain maps to exactly one element in the codomain
b) Each element in the codomain maps to exactly one element in the domain
c) A function can map multiple elements in the domain to the same element in the codomain
d) Every element in the domain has a unique image in the codomain

View Answer

20. What is the ‘order’ of a graph?

a) The number of edges in the graph
b) The number of vertices in the graph
c) The number of cycles in the graph
d) The number of paths in the graph

View Answer

21. What does ‘transitivity’ in a relation imply?

a) If an element a is related to b, and b is related to c, then a is related to c
b) If an element a is related to b, then b is related to a
c) If an element a is related to itself
d) If an element a is not related to b

View Answer

22. What is the ‘intersection’ of two sets?

a) The set containing all elements that are in both sets
b) The set containing all elements in either set
c) The set containing all elements that are not in either set
d) The set containing only elements unique to each set

View Answer

23. In a directed graph, what is an ‘in-degree’ of a vertex?

a) The number of edges entering the vertex
b) The number of edges leaving the vertex
c) The total number of edges connected to the vertex
d) The number of vertices adjacent to the vertex

View Answer

24. Which of the following is true for a bipartite graph?

a) The graph can be colored with two colors such that no two adjacent vertices share the same color
b) The graph contains no edges
c) The graph is a complete graph
d) The graph is a tree

View Answer

25. What is a ‘subgraph’?

a) A graph formed from a subset of vertices and edges of another graph
b) A graph that contains no cycles
c) A graph with exactly one vertex
d) A graph with no edges

View Answer

26. What is the ‘degree’ of a vertex in a graph?

a) The number of edges incident to the vertex
b) The number of cycles containing the vertex
c) The number of vertices connected to the vertex
d) The number of paths through the vertex

View Answer

27. Which of the following is not a property of a tree?

a) It is connected and acyclic
b) It has exactly one path between any two vertices
c) It contains exactly one cycle
d) It has n-1 edges if it has n vertices

View Answer

28. What is the ‘distance’ between two vertices in a graph?

a) The length of the shortest path between them
b) The number of edges between them
c) The number of vertices in the path
d) The number of cycles between them

View Answer

29. What is a ‘cycle’ in a graph?

a) A path that starts and ends at the same vertex with no repeated edges
b) A path that visits every vertex exactly once
c) A set of edges connecting vertices with no common endpoints
d) A sequence of edges that does not form a loop

View Answer

30. Which theorem is used to prove that a graph contains a Hamiltonian cycle?

a) Dirac’s theorem
b) Euler’s theorem
c) Pigeonhole principle
d) Kuratowski’s theorem

View Answer

31. In combinatorics, what does the ‘factorial’ of a number n (n!) represent?

a) The product of all positive integers up to n
b) The sum of all positive integers up to n
c) The number of permutations of n elements
d) Both a and c

View Answer

32. What is a ‘permutation’?

a) An arrangement of objects in a specific order
b) A combination of objects without regard to order
c) The number of ways to choose objects from a set
d) The number of distinct subsets of a set

View Answer

33. Which principle is used to count the number of ways to arrange objects?

a) Inclusion-Exclusion principle
b) Principle of mathematical induction
c) Pigeonhole principle
d) Addition principle

View Answer

34. What does the ‘inclusion-exclusion principle’ help calculate?

a) The size of the union of overlapping sets
b) The size of a single set
c) The size of the intersection of disjoint sets
d) The size of the Cartesian product of sets

View Answer

35. Which of the following is not a type of graph traversal algorithm?

a) Depth-First Search (DFS)
b) Breadth-First Search (BFS)
c) Dijkstra’s algorithm
d) Prim’s algorithm

View Answer

36. What is the ‘adjacency matrix’ of a graph?

a) A matrix where entry (i, j) represents the number of edges between vertex i and vertex j
b) A matrix where entry (i, j) represents the degree of vertex i
c) A matrix that represents the distances between vertices
d) A matrix representing the path lengths in the graph

View Answer

37. In logic, what is a ‘proposition’?

a) A statement that is either true or false
b) A collection of statements
c) An argument consisting of multiple statements
d) A method for proving theorems

View Answer

38. What does the ‘distributive law’ state in Boolean algebra?

a) A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C)
b) A ∨ (B ∧ C) = (A ∨ B) ∧ (A ∨ C)
c) A ∧ B = B ∧ A
d) A ∨ B = B ∨ A

View Answer

39. In graph theory, what is the ‘minimum spanning tree’?

a) A tree that spans all vertices with the minimum possible total edge weight
b) A tree that spans all vertices with the maximum possible total edge weight
c) A tree that includes all edges in the graph
d) A tree with exactly two vertices

View Answer

40. What is a ‘strongly connected’ directed graph?

a) A graph where there is a path from any vertex to any other vertex
b) A graph where all vertices are connected by edges
c) A graph with a cycle
d) A graph with exactly one vertex

View Answer

41. What does ‘Kuratowski’s theorem’ describe?

a) The characterization of planar graphs
b) The existence of Hamiltonian cycles
c) The existence of Eulerian paths
d) The maximum flow in a network

View Answer

42. In Boolean algebra, what is the identity law?

a) A ∧ 1 = A
b) A ∨ 0 = A
c) A ∧ 0 = 0
d) Both a and b

View Answer

43. Which algorithm is used to find the shortest path in a graph with negative weights?

a) Bellman-Ford algorithm
b) Dijkstra’s algorithm
c) Floyd-Warshall algorithm
d) Prim’s algorithm

View Answer

44. What is an ‘isomorphism’ between two graphs?

a) A bijective mapping between the vertex sets that preserves the edge relations
b) A mapping that changes edge weights
c) A process of adding new vertices to the graph
d) A way to delete edges from the graph
View Answer

45. What is the ‘Eulerian circuit’ in a graph?

a) A circuit that visits every edge exactly once and returns to the starting vertex
b) A circuit that visits every vertex exactly once
c) A circuit that avoids certain edges
d) A path that covers all edges

View Answer

46. What is the ‘matrix representation’ of a graph?

a) A matrix where rows and columns represent vertices and entries represent edges
b) A matrix where rows and columns represent edges and entries represent vertices
c) A matrix representing vertex degrees
d) A matrix representing distances between vertices

View Answer

47. What is a ‘subgraph’?

a) A graph formed from a subset of vertices and edges of another graph
b) A graph that includes all edges of a graph
c) A graph with no cycles
d) A graph with no edges

View Answer

48. What is ‘graph coloring’?

a) The assignment of colors to vertices so that no two adjacent vertices share the same color
b) The assignment of colors to edges
c) The process of removing edges from a graph
d) The process of adding vertices to a graph

View Answer

49. What is the ‘Lattice’ in discrete mathematics?

a) A partially ordered set in which every pair of elements has a unique supremum and infimum
b) A complete graph with all vertices connected
c) A graph with no cycles
d) A set of disjoint sets

View Answer

50. What is ‘congruence’ in modular arithmetic?

a) Two numbers are congruent if they have the same remainder when divided by a given modulus
b) Two numbers are congruent if they have the same value
c) Two numbers are congruent if their sum is divisible by the modulus
d) Two numbers are congruent if their product is divisible by the modulus

View Answer

51. What is a ‘Hasse diagram’?

a) A diagram representing the partial order of a set
b) A diagram representing all possible graph edges
c) A diagram showing vertex distances
d) A diagram illustrating graph cycles

View Answer

52. In graph theory, what does a ‘vertex cover’ represent?

a) A set of vertices that touches all edges in the graph
b) A set of edges that connects all vertices
c) A subset of vertices with no edges between them
d) A set of paths covering all vertices

View Answer

53. What is the ‘Handshaking Lemma’?

a) The sum of degrees of all vertices in a graph is twice the number of edges
b) The sum of all edge weights is equal to the number of vertices
c) Each vertex in a graph has an equal number of edges
d) The number of edges is always greater than the number of vertices

View Answer

54. What is a ‘Directed Acyclic Graph’ (DAG)?

a) A directed graph with no cycles
b) A graph where every pair of vertices is connected
c) A graph with only undirected edges
d) A graph with a single vertex

View Answer

55. What does the ‘Floyd-Warshall algorithm’ compute?

a) Shortest paths between all pairs of vertices
b) Minimum spanning tree
c) Shortest path from a single source vertex
d) Maximum flow in a network

View Answer

56. In Boolean algebra, what is the ‘De Morgan’s Law’?

a) ¬(A ∧ B) = ¬A ∨ ¬B
b) ¬(A ∨ B) = ¬A ∧ ¬B
c) A ∨ ¬A = 1
d) Both a and b

View Answer

57. What is the ‘power set’ of a set A?

a) The set of all subsets of A
b) The set of all elements of A
c) The set of all elements not in A
d) The set of all elements in the Cartesian product of A with itself

View Answer

58. In combinatorics, what is a ‘combination’?

a) A selection of objects where order does not matter
b) An arrangement of objects where order matters
c) The number of permutations of a set
d) The number of distinct subsets of a set
View Answer

59. What does the ‘Euler’s formula’ relate in graph theory?

a) The number of vertices, edges, and faces in a planar graph
b) The number of paths in a graph
c) The number of cycles in a graph
d) The number of ways to color a graph

View Answer

60. What is the ‘transitive closure’ of a relation?

a) The smallest transitive relation containing the original relation
b) The largest non-transitive relation
c) The complement of the relation
d) The intersection of all transitive relations

View Answer

61. What is ‘set union’?

a) A set containing all elements that are in either of two sets
b) A set containing all elements that are in both sets
c) A set containing only the elements that are unique to each set
d) A set containing the difference between two sets

View Answer

62. What is the ‘Kruskal’s algorithm’ used for?

a) Finding the minimum spanning tree of a graph
b) Finding the shortest path in a graph
c) Finding the maximum flow in a network
d) Finding the longest path in a graph

View Answer

63. What is a ‘complete bipartite graph’?

a) A bipartite graph where every vertex in one set is connected to every vertex in the other set
b) A bipartite graph with no edges
c) A graph where every vertex is connected to every other vertex
d) A graph with exactly two disjoint sets

View Answer

64. What is the ‘principle of inclusion-exclusion’ used for in combinatorics?

a) Counting the number of elements in the union of overlapping sets
b) Counting the number of elements in the intersection of sets
c) Finding the number of disjoint subsets
d) Calculating permutations of sets

View Answer

65. What is the ‘degree sequence’ of a graph?

a) A list of vertex degrees in a non-increasing order
b) The total number of vertices in a graph
c) A list of edge weights in ascending order
d) The number of cycles in the graph

View Answer

66. What is a ‘strongly connected component’ in a directed graph?

a) A maximal subset of vertices where each vertex is reachable from any other vertex
b) A subset of vertices with no edges between them
c) A subset of vertices with exactly one incoming edge
d) A subset of vertices with exactly one outgoing edge

View Answer

67. In graph theory, what is a ‘clique’?

a) A subset of vertices where every pair is connected by an edge
b) A subset of vertices with no edges between them
c) A single vertex
d) A sequence of edges

View Answer

68. What is a ‘Hamiltonian path’?

a) A path that visits every vertex exactly once
b) A path that visits every edge exactly once
c) A path that includes a cycle
d) A path with the maximum number of edges

View Answer

69. What does the ‘Prim’s algorithm’ find in a graph?

a) The minimum spanning tree
b) The shortest path between vertices
c) The maximum flow in a network
d) The longest path in a graph

View Answer

70. In graph theory, what is the ‘cut’ of a graph?

a) A partition of the vertices into two disjoint sets
b) A subset of edges that separates the graph into two parts
c) The number of edges in the graph
d) The number of vertices in the graph

View Answer

71. What is the ‘Huffman coding’ used for?

a) Compressing data using variable-length codes
b) Encrypting data
c) Error detection in data transmission
d) Sorting data

View Answer

72. What is the ‘Kuratowski’s theorem’ used for in graph theory?

a) To characterize planar graphs
b) To find Hamiltonian cycles
c) To determine Eulerian paths
d) To count graph colorings

View Answer

73. What is a ‘regular graph’?

a) A graph where every vertex has the same degree
b) A graph where all vertices are connected
c) A graph with exactly two cycles
d) A graph where every vertex is connected to every other vertex

View Answer

74. What is the ‘Euler’s formula’ in planar graph theory?

a) V – E + F = 2
b) V + E = F
c) E – V = F
d) V + E + F = 0

View Answer

75. What is the ‘recursive relation’ in combinatorics?

a) A relation defining a sequence where each term is defined in terms of previous terms
b) A relation defining a sequence in terms of all previous terms
c) A relation defining terms without any dependencies
d) A relation defining a set of unique elements

View Answer

76. What is ‘strong connectivity’ in a directed graph?

a) A property where there is a path from any vertex to every other vertex
b) A property where every vertex is connected by edges
c) A property where all edges are directed towards a single vertex
d) A property where no paths exist between vertices
View Answer

77. In set theory, what is the ‘Cartesian product’ of two sets A and B?

a) A set of ordered pairs where the first element is from A and the second is from B
b) A set containing all elements in either A or B
c) A set containing all elements that are in both A and B
d) A set containing all elements not in A or B

View Answer

78. What is the ‘generating function’ in combinatorics?

a) A formal power series whose coefficients represent a sequence
b) A function that generates random numbers
c) A function that defines the distance between elements
d) A function that calculates permutations

View Answer

79. What is a ‘minimal spanning tree’ in graph theory?

a) A spanning tree with the minimum possible total edge weight
b) A spanning tree with the maximum possible total edge weight
c) A spanning tree with exactly two edges
d) A spanning tree with the maximum number of vertices

ViewAnswer

80. In combinatorics, what does ‘binomial coefficient’ represent?

a) The number of ways to choose k elements from a set of n elements
b) The number of ways to arrange n elements
c) The number of ways to partition a set into k subsets
d) The number of distinct permutations of a set

View Answer

81. What is a ‘graph homomorphism’?

a) A mapping between graphs that preserves the adjacency relationship
b) A mapping that changes edge weights
c) A process of merging two graphs
d) A way to remove edges from a graph

View Answer

82. What is the ‘Chromatic Number’ of a graph?

a) The minimum number of colors needed to color the vertices so that no two adjacent vertices share the same color
b) The number of edges in the graph
c) The number of vertices in the graph
d) The maximum degree of any vertex

View Answer

83. What does ‘Hamiltonian graph’ mean?

a) A graph that contains a Hamiltonian cycle
b) A graph that contains a Eulerian path
c) A graph where every vertex is connected to every other vertex
d) A graph with exactly one cycle

View Answer

84. What is a ‘partition’ in set theory?

a) A division of a set into non-overlapping subsets such that their union is the original set
b) A way to combine two sets into one
c) A division of a set into equal-sized subsets
d) A selection of elements from a set without regard to order

View Answer

85. In logic, what is a ‘logical connective’?

a) A symbol used to connect propositions to form compound statements
b) A type of logical statement
c) A method for deriving proofs
d) A way to classify logical statements

View Answer

86. What does ‘graph isomorphism’ test?

a) Whether two graphs are structurally identical
b) Whether two graphs have the same number of edges
c) Whether two graphs have the same number of vertices
d) Whether one graph can be obtained from another by adding edges
View Answer

87. What is a ‘cycle graph’?

a) A graph that consists of a single cycle
b) A graph with no cycles
c) A graph where every vertex is connected to every other vertex
d) A graph with multiple disjoint cycles

View Answer

88. What does ‘graph diameter’ measure?

a) The longest shortest path between any two vertices in the graph
b) The shortest path between any two vertices
c) The total number of edges in the graph
d) The number of vertices in the graph

View Answer

89. What is ‘Euler’s theorem’ for planar graphs?

a) A formula relating the number of vertices, edges, and faces in a planar graph
b) A theorem about the existence of Hamiltonian cycles
c) A theorem about the number of spanning trees in a graph
d) A theorem about the number of edges in a complete graph

View Answer

90. What does the ‘Bellman-Ford algorithm’ compute?

a) Shortest paths from a single source vertex in a graph with negative weights
b) Minimum spanning tree
c) Shortest paths between all pairs of vertices
d) Maximum flow in a network

View Answer

91. What is the ‘Floyd-Warshall algorithm’ used for?

a) Finding shortest paths between all pairs of vertices in a weighted graph
b) Finding the maximum flow in a network
c) Finding the minimum spanning tree
d) Finding the shortest path between two vertices

View Answer

92. What is ‘graph connectivity’?

a) A measure of whether there is a path between every pair of vertices
b) A measure of whether the graph contains cycles
c) A measure of the number of vertices in the graph
d) A measure of the number of edges in the graph

View Answer

93. What is a ‘tree’ in graph theory?

a) A connected acyclic graph
b) A graph with exactly one cycle
c) A disconnected graph
d) A graph with multiple cycles

View Answer

94. What is a ‘spanning tree’?

a) A subgraph that includes all vertices and is a tree
b) A subgraph that includes all edges and is a tree
c) A subgraph that includes a subset of edges and vertices
d) A subgraph with no cycles

View Answer

95. What is the ‘Kruskal’s algorithm’ used for?

a) Finding the minimum spanning tree in a weighted graph
b) Finding the shortest path between two vertices
c) Finding the maximum flow in a network
d) Finding the longest path in a graph

View Answer

96. What is a ‘Hamiltonian cycle’?

a) A cycle that visits every vertex exactly once and returns to the starting vertex
b) A cycle that visits every edge exactly once
c) A cycle with the maximum number of edges
d) A cycle with exactly two vertices

View Answer

97. What is a ‘bipartite graph’?

a) A graph where vertices can be divided into two disjoint sets such that no two vertices within the same set are adjacent
b) A graph where every vertex is connected to every other vertex
c) A graph with exactly two cycles
d) A graph where every vertex is connected to exactly two other vertices

View Answer

98. What is ‘graph coloring’?

a) Assigning colors to vertices so that no two adjacent vertices share the same color
b) Coloring edges in a graph
c) Coloring vertices such that every vertex is colored the same
d) Assigning colors randomly to vertices

View Answer

99. What does the ‘Pigeonhole Principle’ state?

a) If more items are put into fewer containers than there are items, then at least one container must hold more than one item
b) If items are distributed evenly among containers, each container will hold the same number of items
c) Each container will hold exactly one item
d) If fewer items are put into more containers, each container will hold at most one item

View Answer

100. What is a ‘K-regular graph’?
a) A graph where every vertex has exactly k edges
b) A graph where every vertex has the same degree
c) A graph with exactly k vertices
d) A graph with exactly k edges
View Answer