Introduction
Graph data structures are among the most essential and intriguing subjects to study in computer science because of their use in realworld applications such as google maps and circuit design.
Formally, a graph is a nonlinear 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.

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.

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.

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

Graph G is formed by adding vertex s to K_{3,4} and making s adjacent to all of K_{3,4}. The bare minimum of colors necessary to edgecolor 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.

The bare minimum of colors necessary to vertexcolor 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 fourcolor theorem is used here.
According to the property of fourcolor theorems and planar graphs, the maximum number of colors that are needed to vertexcolor any planar graph is 4.

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(n^{2})
(D) O(mn)
Answer: C. O(n^{2})
Explanation: When a graph is represented using an adjacency list, a depthfirst 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. (n^{2})

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 selfloops 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 selfloops and no multiple edges).

Consider graph G, which is undirected and unweighted. Starting at node r, perform a breadthfirst 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 breadthfirst 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)

How many undirected graphs (not necessarily connected) may be made from a set of x vertices V= {V1, V2,…Vx)?
(A) x(xl)/2
(B) 2^{x}
(C) x!
(D) 2^{(x(x1)/2)}
Answer: D. 2^{(x(x1)/2)}
Explanation: There can only be x(x1)/2 edges in an undirected graph. Any of the x(x1)/2 edges can be chosen. So there are 2^{(x(x1)/2)} total undirected graphs with x vertices.

In a depthfirst 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.