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 1

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. A bridge is an edge that disconnects a graph in a connected graph when removed. Which of the following is correct?
    (A) No bridges in a tree
    (B) A bridge cannot be included in a simple cycle.
    (C) Every edge of a clique with a size ≥ 3 is a bridge
    (D) A cycle cannot exist in a graph with bridges.

    Answer: B. A bridge cannot be included in a simple cycle.
    Explanation: If an edge is part of the cycle, its removal will not disconnect the graph.

     
  2. Assume a connected planar graph with six vertices of degree four. A planar representation of this graph divides the plane into how many regions?
    (A) 6
    (B) 8
    (C) 12
    (D) 20

    Answer: B. 8
    Explanation: According to the handshaking theorem, the sum of the degree of vertices = 2 * the number of edges(e).
    4+4+4+4+4+4=2∗e
    e=12
    Also, according to Euler's formula,
    r=e−v+2
    r=12−6+2
    r=12−6+2
    r=8
    Hence, Option B. is correct.
     
  3. Let δ signify a vertex's minimum degree in a graph. Which of these statements are TRUE for every planar graph with n vertices and δ≥3?
    (A) In any planar embedding, the number of faces is at least (n/2)+2.
    (B) In any planar embedding, the number of faces is less than (n/2)+2.
    (C)There is a planar embedding in which the number of faces is less than  (n/2)+2.
    (D)There is a planar embedding in which the number of faces is at most n/(δ+1).

    Answer: A.  In any planar embedding, the number of faces is at least (n/2)+2.
    Explanation: 
    Euler’s formula for connected graph = n – e + f = 2 (n=No. Of vertices, e= No. Of edges, f= No. Of faces).
    Since the degree of every vertex is at least 3, from the handshaking lemma 3n ≤ 2e.
    3n/2 ≤ e 
    Putting these values in Euler's formula. 
    n - 3n/2 +n ≥ 2 
    f ≥ n/2 + 2
     
  4. Graph G is formed by adding vertex s to K3,4 and making s adjacent to all of K3,4. The bare minimum of colors necessary to edge-color G is _______
    (A) 3
    (B) 7
    (C) 9
    (D) 11

    Answer: B. 7
    Explanation: We have to find a solution for edge coloring rather than vertex coloring.
    If the question were about vertex coloring, the answer would be 3.
    Edge coloring for graphs assigns colors to graph edges so that no two incident edges have the same color.
    The vertex with the most incident edges is 's' as it has an edge to every other vertex in the graph. So these vertices have 7 incident edges, each of which must be assigned a different/unique color.
    Hence, the minimum number of colors required to color the edge in the given graph is 7.
     
  5. The bare minimum of colors necessary to vertex-color any planar graph is ________
    (A) 1
    (B) 4
    (C) 3
    (D) 2

    Answer: B . 4
    Explanation: 
    A planar graph is a graph on a plane in which no two edges intersect. A map's set of regions can be more abstractly represented as an undirected graph with a vertex for each region and an edge for every pair of regions that share a boundary segment. Hence, the four-color theorem is used here.
    According to the property of four-color theorems and planar graphs, the maximum number of colors that are needed to vertex-color any planar graph is 4.
     
  6. Consider graph G, which has n vertices and m edges. What is the tightest upper bound on G's Depth First Search running time? Assume that a matrix of adjacencies represents the graph.
    (A) O(n)
    (B) O(m+n)
    (C) O(n2)
    (D) O(mn)

    Answer: C. O(n2)
    Explanation: When a graph is represented using an adjacency list, a depth-first search requires O(m+n) time.
    The graph is represented as a "n x n" matrix in adjacency matrix representation. To do DFS, we traverse the row that corresponds to each vertex to discover all nearby vertices (In adjacency list representation we traverse only the adjacent vertices of the vertex). Hence, the time complexity is O. (n2)
     
  7. If the sequence of the degrees of the nodes in the graph in decreasing order then it is called the degree sequence of a simple graph. Which of the following sequences can never be the graph's degree sequence?
    7, 6, 5, 4, 4, 3, 2, 1
    6, 6, 6, 6, 3, 3, 2, 2
    7, 6, 6, 4, 4, 3, 2, 2
    8, 7, 7, 6, 4, 2, 1, 1

    (A) 1 and 2
    (B) 3 and 4
    (C) 4 only
    (D) 2 and 4
    Answer: D. 2 and 4
    Explanation: We have a vertex of degree 8 in sequence IV, which is impossible to achieve in a basic graph (no self-loops or multiple edges) with a total vertex count of 8. In such a graph, the maximum degree achievable is 7.

    our vertices are connected to six other vertices in sequence II, but the remaining four vertices have degrees of 3, 3, 2, and 2, which are not feasible in a simple graph (no self-loops and no multiple edges).

     
  8. Consider graph G, which is undirected and unweighted. Starting at node r, perform a breadth-first traversal of G. Let d(l, u) and d(l, v) be the lengths of the shortest paths from l to u and v, respectively, in G. Which of the following statements is valid if u is visited before v during the breadth-first traversal?
    (A) d(l, u) < d (l, v)
    (B)d(l, u) > d(l, v)
    (C)d(l, u) <= d (l, v)
    (D)None of the above

    Answer: C. d(l, u) <= d (l, v)
    Explanation: d(l, u) and d(l, v) will be equal when u and v are at the same level, otherwise d(l, u) will be less than d(l, v)

     
  9. How many undirected graphs (not necessarily connected) may be made from a set of x vertices V= {V1, V2,…Vx)?
    (A) x(x-l)/2
    (B) 2x
    (C) x!
    (D) 2(x(x-1)/2)

    Answer: D. 2(x(x-1)/2)
    Explanation: There can only be x(x-1)/2 edges in an undirected graph. Any of the x(x-1)/2 edges can be chosen. So there are 2(x(x-1)/2) total undirected graphs with x vertices.

     
  10. In a depth-first traversal(DFS) of a graph G with x vertices, e edges are marked as tree edges. What will be the total number of connected components in G?
    (A) e
    (B) e + 1
    (C) x – e – 1
    (D) x – e
    Answer: D. x – e
    Explanation: The edges of the DFS tree are called tree edges. There are n+1 vertices in a tree if there are n tree edges.

 

Refer to Gate Questions on Graph: Part 2 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. Why are graphs important data structures? 
    The graphs in data structures are important since they can easily represent the relations between real-life data.  
     
  2. In what way a tree and a graph are different?
    A tree is a type of graph that does not contain any cycles. So, while every tree is a graph, not every graph is a tree.
     
  3. What are the real-life applications of graphs? 
    Facebook's graph API, knowledge graphs, path optimization methods for determining the shortest path between locations, GPS navigation systems, and chemistry, graphs reflect social groups.
     
  4. How do directed and undirected graphs differ?
    A directed graph has ordered pairings of vertices, whereas an undirected graph has unordered pairs of vertices. Edges in a directed graph represent the direction of vertices, but edges in an undirected graph do not.
     
  5. What is the maximum number of edges in the undirected graph of Nodes N? 
    In an undirected network, each node can have the edge over every other N-1 node. As a result, the total number of edges possible is N * (N - 1), yet in the undirected graph, the two edges between two nodes are the same. As a result, one of them must be removed. As a result, the total number of edges is N * (N - 1)/2.

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
Heap
Next article
Gate Questions on Graph - Part 2
Live masterclass