Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Gate Questions on Graph
3.
Frequently asked Questions
4.
Conclusion
Last Updated: Mar 27, 2024

Gate Questions on Graph - Part 2

Author SAURABH ANAND
1 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

Graph data structures are among the most essential and intriguing subjects to study in computer science because of their use in real-world applications such as google maps and circuit design.

Formally, a graph is a non-linear data structure consisting of nodes and the edges that connect them.

You can check out our top graph problems.

This blog covers the previous year's gate questions on graph with proper explanation.

Gate Questions on Graph

Let us now discuss the previously asked gate questions on Graph.

 

  1. There are eight vertices and five faces in an undirected connected planar graph G. The number of edges in G is _________.
    (A) 10
    (B) 11
    (C) 12
    (D) 6

    Answer: B. 11
    Explanation: By using Euler’s theorem, the number of regions(R) = e – v + 2
    R = e – v + 2
    5 = e – 8 + 2 = e-6
    e = 5 + 6 = 11
     
  2. Let a simple graph G with 20 vertices and 8 components. If we delete a vertex in G, then the number of components in G should lie between ____.
    (A) 8 and 20
    (B)  8 and 19
    (C)  7 and 19
    (D)  7 and 20

    Answer: C.  7 and 19
    Explanation: If the vertex we are deleting from G is an isolated vertex, which is a component by itself, then the number of components in G becomes 7.
    If G is a start Graph, then by deleting the cut vertex of G, we get 19 components.
     
  3. Let a graph G with 100 vertices numbered from 1 to 100. Two vertices x and y are adjacent iff |x−y|=12 or |x−y|=8. The number of connected components in G is
    (A) 4
    (B) 8
    (C) 25
    (D) 12

    Answer: B. 4
    Explanation: When vertices are arranged with the difference of 8 there are 8 components, as shown by 8 columns in the image below



    Source: https://edurev.gumlet.io/ApplicationImages/Temp/3954df8f-5d1b-410a-aaa3-ba1e3b0a15e5_lg.png?w=768&dpr=1.0

    When vertices are arranged with the difference of 12, the number of components is reduced to 4 as the first column will be connected with the fifth column, the second column will be connected with the sixth column, the third column will be connected with the seventh column and fourth column will be connected with the 8 columns. No other form of connection is there, so a total of 4 connected components are there.
     
  4. How many edges may an acyclic undirected graph with n vertices have?
    (A) n + 1
    (B) n - 1
    (C) n
    (D) 2n - 1

    Answer: B. n - 1
    Explanation: When cyclic, n * (n – 1) / 2. However, the acyclic graph with the most edges is actually a spanning tree. Hence the right answer is n-1 edges.
     
  5. Let a weighted undirected graph G and e be an edge with the greatest weight in G. Assume G has a minimum weight spanning tree with the edge e. Which of the following propositions is consistently TRUE?
    (A) Edge e cannot be contained in a cycle.
    (B)  In G, there is a cycle with all edges of maximal weight.
    (C) A cutset in G has all edges of maximum weight.
    (D)  All edges in G have the same weight

    Answer: C.  There exists a cutset in G having all edges of maximum weight.
    Explanation: Option C asserts that if e is in the minimum spanning tree, there must be a cut-set (minimum edge set whose removal disconnects the graph) in G with all edges of the greatest weight. And it is correct.
     
  6. Which of the following properties apply to the adjacency matrix X of a simple undirected unweighted network with n nodes?
    (A) If the sum of all the elements of X is at most 2(n−1), then the graph must be acyclic.
    (B) If the graph is connected, none of the entries of Xn−1+In can be zero.
    (C) If there is at least a 1 in each of X’s rows and columns, the graph must be connected.
    (D) The diagonal entries of X2 are the degrees of the graph's vertices.

    Answer: D. The diagonal entries of X2 are the degrees of the graph's vertices.
    Explanation: X2 diagonal elements = (1.1 or 0.0)+(1.1 or 0.0) + ….. +(1.1 or 0.0)  [ n times ]
    let some specific node C, if C - A edge present, then 1.1 instead of 0.0 with respect to node A in above eqation
    therefore for each edge between C and Vertex, there should be one 1 in the above equation
    Therefore X2 diagonal elements = degree of the vertices of the graph.
     
  7. In a bipartite graph on 12 vertices, what is the maximum number of edges present  _________?
    (A) 32
    (B) 35
    (C) 46
    (D) 36

    Answer: D. 36
    Explanation:  We know, Maximum possible number of edges in a bipartite graph on ‘n’ vertices = (1/4) x n2.
    Substituting n = 12, we get the maximum number of edges in a bipartite graph on 12 vertices.
    = (1/4) x (12)2
    = (1/4) x 12 x 12
    = 36
     
  8. Which of the following claims about an undirected graph is/are TRUE?
    P: The number of vertices with odd degrees is even.
    Q: The sum of all vertices' degrees is even.
    (A) Q
    (B) P
    (C) Both Q and P
    (D) Neither Q and P

    Answer: C. Both P and Q
    Explanation: Q is correct because the graph is undirected, and each edge adds 2 to the sum of degrees.
    P is correct: If we take the sum of all degrees and deduct all even degrees, we get an even number (because Q is true). As a result, the total number of
    odd degree vertices must be even.
     
  9. What is the time complexity of the Bellman-Ford single-source shortest path algorithm on a complete graph of n vertices?
    (A) Θ(n3)
    (B) Θ(n2 Logn)
    (C) Θ(n2)
    (D) Θ(n3 Logn)

    Answer: A. Θ(n3)
    Explanation: The time complexity of the Bellman-Ford algorithm is Θ(VE), where V denotes the number of vertices and E denotes the number of edges. When the graph is finished, the value of E becomes Θ(V2). Hence, the overall time complexity becomes Θ(V3).
     
  10. What is the number of an m-vertex simple connected graph which does not contain any odd-length cycle? Assume m >= 2.
    (A) 3
    (B) 2
    (C) m-1
    (D) m

    Answer: B. 2
    Explanation: The chromatic number of a graph is the smallest number of colors needed to color the vertices so that no two adjacent vertices share the same color. 
     

Refer to Gate Questions on Graph: Part 1 for more questions. Also, check out the Gate Syllabus for CSE.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently asked Questions

  1. How can we implement BFS? 
    A queue can be used to implement BFS. We keep adding nodes from the same level to the queue and removing nodes from the previous level from the queue. When we finish traversing one level, all of the nodes on the next level are in the queue.  
     
  2. In graph theory, what is a cycle?
    A cycle is a path that begins at one vertex and finishes at the same vertex.
     
  3. A triangle-free graph with n vertex contains how many edges?
    A triangle-free graph with n vertex contains (n2)/4 edges.
     
  4. What is the other name of the complete bipartite graph?
    A complete bipartite graph is also known as a biclique graph.

Conclusion

In this article, we have gone through important previous years' gate questions on Graph.

We hope that this blog has helped you enhance your knowledge of previous years’ gate questions on Graph and if you would like to learn more, check out our articles on gate questions on web technologies. Do upvote our blog to help other ninjas grow. Happy Coding!

Previous article
Gate Questions on Graph - Part 1
Next article
Hash
Live masterclass