Discrete Mathematics Questions and Answers – Graph
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.