250+ TOP MCQs on Trees – Cycles and Answers

Discrete Mathematics Multiple Choice Questions on “Trees – Cycles”.

1. If two cycle graphs Gm and Gn are joined together with a vertex, the number of spanning trees in the new graph is ______
a) m+n-1
b) m-n
c) m*n
d) m*n+1

Answer: c
Clarification: As there are n possible edges to be removed from G and m edges to be removed from G and the rest from a spanning tree so the number of spanning tree in the new graph is m*n.

2. For an n-vertex undirected graph, the time required to find a cycle is ____________
a) O(n)
b) O(n²)
c) O(n+1)
d) O(logn)

Answer: a
Clarification: The existence of a cycle in directed and undirected graphs can be determined by depth-first search (DFS) of the graph finds an edge that points to an ancestor of the current vertex. In an undirected graph, finding any already visited vertex will indicate a back edge. All the back edges which DFS skips over are part of cycles. In the case of undirected graphs, only O(n) time is required to find a cycle in an n-vertex graph, since at most n − 1 edges can be tree edges.

3. A binary cycle space forms a ______ over the two element field.
a) triangular graph
b) vector space
c) binary tree
d) hamiltonian graph

Answer: b
Clarification: The term cycle refers to an element of the cycle space of a graph. There are many cycle spaces. The most common is the binary cycle space, which contains the edge sets that have even degrees at every vertex and it forms a vector space over the two-element field.

4. If G is a simple graph with n-vertices and n>=3, the condition for G has a Hamiltonian circuit is __________
a) the degree of each vertex is at most n/2
b) the degree of each vertex is equal to n
c) the degree of every vertex is at least n+1/2
d) the degree of every vertex in G is at least n/2

Answer: d
Clarification: A simple circuit in a graph G that passes through every vertex exactly once is called a Hamiltonian circuit. If there is a vertex of degree one in a graph then it is impossible for it to have a Hamiltonian circuit. If G is a simple graph with n-vertices and n>=3 such that the degree of every vertex in G is at least n/2, then G has a Hamiltonian circuit.

5. What is a separable graph?
a) A disconnected graph by deleting a vertex
b) A disconnected graph by removing an edge
c) A disconnected graph by removing one edge and a vertex
d) A simple graph which does not contain a cycle

Answer: a
Clarification: By deletion of a vertex the graph is disconnected and the graph is called separable graph and the vertex is called cut vertex.

6. How many edges are there in a complete graph of order 9?
a) 35
b) 36
c) 45
d) 19

Answer: b
Clarification: In a complete graph of order n, there are n*(n-1) number of edges and degree of each vertex is (n-1). Hence, for a graph of order 9 there should be 36 edges in total.

7. How many cycles are there in a wheel graph of order 5?
a) 6
b) 10
c) 25
d) 7

Answer: d
Clarification: In a cycle of a graph G if we join all the vertices to the centre point, then that graph is called a wheel graph. There is always a Hamiltonian cycle in a wheel graph and there are n²-3n+3 cycles. So, for order 5 the answer should be 7.

8. The time complexity to find a Eulerian path in a graph of vertex V and edge E is _____________
a) O(V²)
b) O(V+E-1)
c) O(V+E)
d) O(E+1)

Answer: c
Clarification: An undirected graph has Eulerian Path if the following two conditions are true: -a) All vertices with a non-zero degree are connected. A graph of vertices with zero degrees don’t belong to Eulerian Cycle or Path, b) If two vertices have odd degree and all other vertices have even degree. Thus, the time to find whether a graph has a Eulerian path or not is O(V+E) with V vertices and E edges.

9. The time complexity to find shortest distances by using Dijkstra’s algorithm is __________
a) O(E²)
b) O(V+1-E)
c) O(V+E)
d) O(E+VlogV)

Answer: d
Clarification: Time complexity of finding shortest distance can be O(E + VLogV) using Fibonacci Heap. The reason is that Fibonacci Heap takes O(1) time for decrease-key operation while Binary Heap takes O(logn) time.

10. Topological sorting of a graph represents _______ of a graph.
a) linear probing
b) linear ordering
c) quadrilateral ordering
d) insertion sorting

Answer: b
Clarification: Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering. If the graph is not a DAG, topological sorting for a graph is not possible.