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{2024-1} &\textbf{2024-2} &\textbf{2023} &\textbf{2022} & \textbf{2021-1}&\textbf{2021-2}&\textbf{Minimum}&\textbf{Average}&\textbf{Maximum}
\\\hline\textbf{1 Mark Count} &1&1&0& 1&1&0&0&0.83&1
\\\hline\textbf{2 Marks Count} &1&2&1& 3 &1&0&0&1.33&3
\\\hline\textbf{Total Marks} & 3&5&2&7 &3&0&\bf{0}&\bf{3.33}&\bf{7}\\\hline
\end{array}}}$$

Filter

Highest voted questions in Graph Theory

#81
3.1k
views
2 answers
17 votes
TIFR CSE 2017 | Part B | Question: 13
For an undirected graph $G=(V, E)$, the line graph $G'=(V', E')$ is obtained by replacing each edge in $E$ by a vertex, and adding an edge between two vertices in $V'$ if...
User Avatar
#82
2.5k
views
1 answers
17 votes
Haming Distance and Chromatic Number
Consider the undirected graph G defined as follows. The vertices are bit string of length 5. We have an edge between vertex “a” and vertex “b” iff “a” and “...
User Avatar
#83
3.1k
views
3 answers
17 votes
TIFR CSE 2012 | Part B | Question: 2
In a graph, the degree of a vertex is the number of edges incident (connected) on it. Which of the following is true for every graph $G$?There are even number of vertices...
User Avatar
#84
7.2k
views
2 answers
17 votes
GATE CSE 2011 | Question: 17
K4 and Q3 are graphs with the following structures.Which one of the following statements is TRUE in relation to these graphs?K4 is a planar while Q3 is notBoth K4 and Q3 ...
User Avatar
#85
2.3k
views
2 answers
16 votes
CMI2015-A-05
An undirected graph has $10$ vertices labelled $1, 2,\dots , 10$ and $37$ edges. Vertices $1, 3, 5, 7, 9$ have degree $8$ and vertices $2, 4, 6, 8$ have degree $7.$ What ...
User Avatar
#86
11.1k
views
3 answers
16 votes
number of perfect matching in complete graph
Is there a way to find no of perfect matchings in a complete graph Kn where n could be either even or odd..?
User Avatar
#87
8.5k
views
2 answers
16 votes
GATE CSE 2005 | Question: 47
Which one of the following graphs is NOT planar? G1G2G3G4
User Avatar
#88
2.5k
views
3 answers
15 votes
ISI Entrance Exam MTech (CS)
Consider all possible trees with $n$ nodes. Let $k$ be the number of nodes with degree greater than $1$ in a given tree. What is the maximum possible value of $k$?
User Avatar
#89
4.1k
views
4 answers
15 votes
GATE CSE 1988 | Question: 2xvi
Write the adjacency matrix representation of the graph given in below figure.
User Avatar
#90
1.9k
views
3 answers
15 votes
GATE CSE 1987 | Question: 9c
Show that the number of odd-degree vertices in a finite graph is even.
User Avatar
#91
7.8k
views
3 answers
14 votes
GATE CSE 2022 | Question: 27
Consider a simple undirected unweighted graph with at least three vertices. If $\textit{A}$ is the adjacency matrix of the graph, then the number of $3–$cycles in the g...
User Avatar
#92
7.8k
views
2 answers
14 votes
GATE CSE 2022 | Question: 40
The following simple undirected graph is referred to as the Peterson graph.Which of the following statements is/are $\text{TRUE}?$The chromatic number of the graph is $3....
User Avatar
#93
3.3k
views
3 answers
14 votes
CMI2013-B-02
A complete graph on $n$ vertices is an undirected graph in which every pair of distinct vertices is connected by an edge. A simple path in a graph is one in which no vert...
User Avatar
#94
798
views
1 answers
13 votes
GO Classes Test Series 2024 | Mock GATE | Test 14 | Question: 15
Let $\mathrm{G}$ be a simple undirected graph on 8 vertices such that there is a vertex of degree 1 , a vertex of degree 2 , a vertex of degree 3 , a vertex of degree 4, ...
User Avatar
#95
8.4k
views
5 answers
13 votes
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 _________.
User Avatar
#96
1.5k
views
2 answers
11 votes
ISI2015-PCB-C3
For a positive integer $n$, let $G = (V, E)$ be a graph, where $V = \text{{0,1}}^n$, i.e., $V$ is the set of vertices has one to one correspondence with the set of all $n...
User Avatar
#97
1.7k
views
1 answers
11 votes
GATE CSE 1987 | Question: 9d
Specify an adjacency-lists representation of the undirected graph given above.
User Avatar
#98
9.2k
views
4 answers
11 votes
ISRO2016-5
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
#99
2.9k
views
2 answers
11 votes
ISRO2007-06
A graph with $n$ vertices and $n-1$ edges that is not a tree, isConnectedDisconnectedEulerA circuit
User Avatar
#100
1.0k
views
1 answers
11 votes
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: Cons...
User Avatar
Page: