Register

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{2022} & \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&1&0&0&1&1&0&1&0&1&0&0.6&1
\\\hline\textbf{2 Marks Count} & 3 &1&0&1&1&1&0&0&0&0&0&0.7&3
\\\hline\textbf{Total Marks} & 7 &3&0&2&3&3&0&1&0&1&\bf{0}&\bf{2}&\bf{7}\\\hline
\end{array}}}$$

Filter

Highest voted questions in Graph Theory

13 votes
5 answers
93
GATE CSE 2021 Set 1 | Question: 16
In an undirected connected planar graph $G$, there are eight vertices and five faces. The number of edges in $G$ is _________.
In an undirected connected planar graph $G$, there are eight vertices and five faces. The number of edges in $G$ is _________.
User Avatar
11 votes
1 answer
95
GATE CSE 1987 | Question: 9d
Specify an adjacency-lists representation of the undirected graph given above.
Specify an adjacency-lists representation of the undirected graph given above.
User Avatar
11 votes
4 answers
96
ISRO2016-5
A given connected graph $\text{G}$ is a Euler Graph if and only if all vertices of $\text{G}$ are of same degree even degree odd degree different degree
A given connected graph $\text{G}$ is a Euler Graph if and only if all vertices of $\text{G}$ are ofsame degree even degreeodd degree ...
User Avatar
11 votes
2 answers
97
ISRO2007-06
A graph with $n$ vertices and $n-1$ edges that is not a tree, is Connected Disconnected Euler A circuit
A graph with $n$ vertices and $n-1$ edges that is not a tree, isConnectedDisconnectedEulerA circuit
User Avatar
11 votes
1 answer
98
CMI2012-B-01
Let $G=(V, E)$ be a graph where $\mid V \mid =n$ and the degree of each vertex is strictly greater than $\frac{n}{2}$. Prove that $G$ has a Hamiltonian path. (Hint: Consider a path of maximum length in $G$.)
Let $G=(V, E)$ be a graph where $\mid V \mid =n$ and the degree of each vertex is strictly greater than $\frac{n}{2}$. Prove that $G$ has a Hamiltonian path. (Hint: Cons...
User Avatar
10 votes
5 answers
99
ISRO2011-35
How many edges are there in a forest with $v$ vertices and $k$ components? $(v+1) - k$ $(v+1)/2 - k$ $v - k$ $v + k$
How many edges are there in a forest with $v$ vertices and $k$ components?$(v+1) - k$$(v+1)/2 - k$$v - k$$v + k$
User Avatar
10 votes
1 answer
100
GATE CSE 1992 | Question: 01,x
Maximum number of edges in a planar graph with $n$ vertices is _____
Maximum number of edges in a planar graph with $n$ vertices is _____
User Avatar
9 votes
1 answer
101
Graph Colouring
The minimum number of colours required to colour the following graph, such that no two adjacent vertices are assigned the same color, is
The minimum number of colours required to colour the following graph, such that no two adjacent vertices are assigned the same color, is
User Avatar
9 votes
1 answer
103
ISRO2009-54
A graph in which all nodes are of equal degree, is known as Multigraph Non regular graph Regular graph Complete graph
A graph in which all nodes are of equal degree, is known asMultigraphNon regular graphRegular graphComplete graph
User Avatar
9 votes
4 answers
104
GATE CSE 1992 | Question: 02,viii
A non-planar graph with minimum number of vertices has $9$ edges, $6$ vertices $6$ edges, $4$ vertices $10$ edges, $5$ vertices $9$ edges, $5$ vertices
A non-planar graph with minimum number of vertices has$9$ edges, $6$ vertices$6$ edges, $4$ vertices$10$ edges, $5$ vertices$9$ edges, $5$ vertices
User Avatar
8 votes
2 answers
105
MadeEasy Test Series 2018: Graph Theory - Graph Coloring
Consider the following graph: Which of the following will represents the chromatic number of the graph? answer given is 4. Please provide a detailed solution.
Consider the following graph: Which of the following will represents the chromatic number of the graph?answer given is 4.Please provide a detailed solution.
User Avatar
8 votes
3 answers
108
ISRO2009-56
A simple graph ( a graph without parallel edge or loops) with $n$ vertices and $k$ components can have at most $n$ edges $n-k$ edges $(n-k) (n-k+1)$ edges $(n-k) (n-k+1)/2$ edges
A simple graph ( a graph without parallel edge or loops) with $n$ vertices and $k$ components can have at most$n$ edges$n-k$ edges$(n-k) (n-k+1)$ edges$(n-k) (n-k+1)/2$ e...
User Avatar
8 votes
1 answer
109
ISRO2009-52
If $\text{G}$ is a graph with e edges and n vertices the sum of the degrees of all vertices in $\text{G}$ is $e$ $e/2$ $e^2$ $2 e$
If $\text{G}$ is a graph with e edges and n vertices the sum of the degrees of all vertices in $\text{G}$ is$e$$e/2$$e^2$$2 e$
User Avatar
8 votes
1 answer
110
ISRO2008-78
Consider the graph shown in the figure below: Which of the following is a valid strong component? $a, c, d$ $a, b, d$ $b, c, d$ $a, b, c$
Consider the graph shown in the figure below:Which of the following is a valid strong component?$a, c, d$$a, b, d$$b, c, d$$a, b, c$
User Avatar
Page: