Graph Theory MCQ Questions - Discrete Mathematics
This section focuses on "Graph" in Discrete Mathematics. These Multiple Choice Questions (mcq) should be practiced to improve the Discrete Mathematics skills required for various interviews (campus interviews, walk-in interviews, company interviews), placements, entrance exams and other competitive examinations.
1. A graph is a set of points, called?
Explanation: A graph is a set of points, called nodes or vertices, which are interconnected by a set of lines called edges
2. Graph consists of a?
Explanation: Graph consists of a non-empty set of vertices or nodes V and a set of edges E.
3. Number of edges incident with the vertex V is called?
Explanation: Degree of a Vertex − The degree of a vertex V of a graph G (denoted by deg (V)) is the number of edges incident with the vertex V.
4. Which of the following is true about Handshaking Lemma?
Explanation: The Handshaking Lemma : In a graph, the sum of all the degrees of all the vertices is equal to twice the number of edges.
5. What is Null Graph?
Explanation: A null graph has no edges.
6. If in a graph multiple edges between the same set of vertices are allowed, it is called?
Explanation: If in a graph multiple edges between the same set of vertices are allowed, it is called Multigraph.
7. The graph in which, there is a closed trail which includes every edge of the graph is known as?
Explanation: A connected graph is called an Euler graph, if there is a closed trail which includes every edge of the graph
8. In a 7-node directed cyclic graph, the number of Hamiltonian cycle is to be
Explanation: A Hamiltonian cycle in a connected graph G is defined as a closed path that traverses every vertex of G exactly once except the starting vertex, at which the path also terminates. In an n-complete graph, there are (n-1)!/2 hamiltonian cycles and so the answer is 360.
9. If G is the forest with 54 vertices and 17 connected components, G has _______ total number of edges.
Explanation: Here we are given a forest with 54 vertices and 17 components. A component is itself a tree and since there are 17 components means that every component has a root, therefore we have 17 roots. Each new vertex of the forest contributes to a single edge to a forest. So for remaining 54-17 = 37 vertices we can have m-n=37 edges. Hence, answer is 37.
10. Triangle free graphs have the property of clique number is __________
Explanation: In an undirected triangle-free graph no three vertices can form a triangle of edges. It can be described as graphs with clique number less than 2 and the graphs with girth greater than 4.