Web Page

Syllabus: Connectivity, Matching, Coloring.

$$\scriptsize{\overset{{\large{\textbf{Mark Distribution in Previous GATE}}}}{\begin{array}{|c|c|c|c|c|c|c|c|}\hline \textbf{Year}&\textbf{2021-1}&\textbf{2021-2}&\textbf{2020}&\textbf{2019}&\textbf{2018}&\textbf{2017-1}&\textbf{2017-2}&\textbf{2016-1}&\textbf{2016-2}&\textbf{Minimum}&\textbf{Average}&\textbf{Maximum} \\\hline\textbf{1 Mark Count}&1&0&0&1&1&0&1&0&1&0&0.55&1 \\\hline\textbf{2 Marks Count}&1&0&1&1&1&0&0&0&0&0&0.44&1 \\\hline\textbf{Total Marks}&3&0&2&3&3&0&1&0&1&\bf{0}&\bf{1.44}&\bf{3}\\\hline \end{array}}}$$

# Recent questions in Graph Theory

1 vote
2 answers
1
In an undirected connected planar graph $G$, there are eight vertices and five faces. The number of edges in $G$ is _________.
3 votes
2 answers
2
Let $G=(V, E)$ be an undirected unweighted connected graph. The diameter of $G$ is defined as: $\text{diam}(G)=\displaystyle \max_{u,v\in V} \{\text{the length of shortest path between$u$and$v$}\}$ Let $M$ be the adjacency matrix of $G$. Define graph $G_2$ on the same set of ... $\text{diam}(G_2) = \text{diam}(G)$ $\text{diam}(G)< \text{diam}(G_2)\leq 2\; \text{diam}(G)$
2 votes
2 answers
3
Let G(V,E) be a simple graph. Let G’(V,E’) be a graph obtained from G such that (u,v) is an edge in G’ if (u,v) is not an edge in G. Which of the following is true? At least one of G or G’ are connected. G is necessarily disconnected. Both G and G’ are disconnected. None of the above.
0 votes
1 answer
4
Degree of each vertex in $K_n$ is $n$ $n-1$ $n-2$ $2n-1$
0 votes
1 answer
5
The number of the edges in a regular graph of degree $’d’$ and $’n’$ vertices is Maximum of $n,d$ $n+d$ $nd$ $nd/2$
3 votes
3 answers
6
Total number of simple graphs that can be drawn using six vertices are: $2^{15}$ $2^{14}$ $2^{13}$ $2^{12}$
1 vote
1 answer
7
If a planner graph, having $25$ vertices divides the plane into $17$ different regions. Then how many edges are used to connect the vertices in this graph. $20$ $30$ $40$ $50$
0 votes
2 answers
8
The number of ways to cut a six sided convex polygon whose vertices are labeled into four triangles using diagonal lines that do not cross is $13$ $14$ $12$ $11$
0 votes
1 answer
9
Maximum degree of any node in a simple graph with $n$ vertices is $n-1$ $n$ $n/2$ $n-2$
1 vote
1 answer
10
Let $G$ be a simple undirected planar graph on $10$ vertices with $15$ edges. If $G$ is a connected graph, then the number of bounded faces in any embedding of $G$ on the plane is equal to: $3$ $4$ $5$ $6$
0 votes
1 answer
11
Given an undirected graph $G$ with $V$ vertices and $E$ edges, the sum of the degrees of all vertices is $E$ $2E$ $V$ $2V$
0 votes
2 answers
12
Which of the following is an advantage of adjacency list representation over adjacency matrix representation of a graph? In adjacency list representation, space is saved for sparse graphs. Deleting a vertex in adjacency list representation is easier than ... matrix representation. Adding a vertex in adjacency list representation is easier than adjacency matrix representation. All of the option.
0 votes
1 answer
13
A path in graph $G$, which contains every vertex of $G$ and only once? Euler circuit Hamiltonian path Euler Path Hamiltonian Circuit
0 votes
1 answer
14
In a given following graph among the following sequences: abeghf abfehg abfhge afghbe Which are depth first traversals of the above graph? I,II and IV only I and IV only II,III and IV only I,III and IV only
0 votes
1 answer
15
Considering the following graph, which one of the following set of edged represents all the bridges of the given graph? $(a,b), (e,f)$ $(a,b), (a,c)$ $(c,d), (d,h)$ $(a,b)$
0 votes
1 answer
16
Which of the following statements is/are TRUE? $S1$:The existence of an Euler circuit implies that an Euler path exists. $S2$:The existence of an Euler path implies that an Euler circuit exists. $S1$ is true. $S2$ is true. $S1$ and $S2$ both are true. $S1$ and $S2$ both are false.
0 votes
1 answer
17
A connected planar graph divides the plane into a number of regions. If the graph has eight vertices and these are linked by $13$ edges, then the number of regions is: $5$ $6$ $7$ $8$
0 votes
0 answers
18
Let $G$ be a simple connected planar graph with $13$ vertices and $19$ edges. Then, the number of faces in the planar embedding of the graph is $6$ $8$ $9$ $13$
0 votes
0 answers
19
The number of diagonals that can be drawn by joining the vertices of an octagon is $28$ $48$ $20$ None of the option
0 votes
0 answers
20
Which of the following statements is/are TRUE for an undirected graph? Number of odd degree vertices is even Sum of degrees of all vertices is even P only Q only Both P and Q Neither P nor Q