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}}}$$

Recent activity in Graph Theory

0 votes
1 answer
1
ISI kolkata MTech CS 2019
Let $K_n$ denote the complete graph on $n$ vertices, with $n ≥ 3$, and let $u$, $v$, $w$ be three distinct vertices of $K_n$. Determine the number of distinct paths from $u$ to $v$ that do not contain the vertex $w$.
Let $K_n$ denote the complete graph on $n$ vertices, with $n ≥ 3$, and let $u$, $v$, $w$ be three distinct vertices of $K_n$. Determine the number of distinct paths fro...
User Avatar
16 votes
3 answers
2
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..?
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
60 votes
10 answers
3
GATE CSE 2003 | Question: 36
How many perfect matching are there in a complete graph of $6$ vertices? $15$ $24$ $30$ $60$
How many perfect matching are there in a complete graph of $6$ vertices?$15$$24$$30$$60$
User Avatar
1 votes
1 answer
6
DRDO CSE 2022 Paper 1 | Question: 10
Given a tree $\text{T}$ and $\lambda \geq 2$ colours $\left(c_{1}, c_{2}, \ldots, c_{\lambda}\right),$ how many proper colourings of the tree $\text{T}$ are possible?
Given a tree $\text{T}$ and $\lambda \geq 2$ colours $\left(c_{1}, c_{2}, \ldots, c_{\lambda}\right),$ how many proper colourings of the tree $\text{T}$ are possible?
User Avatar
9 votes
1 answer
7
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
1 votes
3 answers
8
GATE CSE 2024 | Set 2 | Question: 50
The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. The chromatic number of the following graph is __________.
The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. The chromatic number of the following graph is __________.
User Avatar
0 votes
1 answer
10
DISCRETE
Let T be a tree with n vertices and k be the maximum size of an independent set in T. Then the size of maximum matching in T is (A) k (B) n−k (C) (n−1)/2
Let T be a tree with n vertices and k be the maximum size of an independent set in T. Then the size of maximum matching in T is(A) k(B) n−k(C) (n−1)/2
User Avatar
31 votes
4 answers
11
GATE CSE 1989 | Question: 3-vi
Which of the following graphs is/are planar?
Which of the following graphs is/are planar?
User Avatar
73 votes
6 answers
21
GATE IT 2007 | Question: 25
What is the largest integer $m$ such that every simple connected graph with $n$ vertices and $n$ edges contains at least $m$ different spanning trees ? $1$ $2$ $3$ $n$
What is the largest integer $m$ such that every simple connected graph with $n$ vertices and $n$ edges contains at least $m$ different spanning trees ?$1$$2$$3$$n$
User Avatar
7 votes
3 answers
22
ISRO2018-38
The number of edges in a regular graph of degree: $d$ and $n$ vertices is: maximum of $n$ and $d$ $n +d$ $nd$ $nd/2$
The number of edges in a regular graph of degree: $d$ and $n$ vertices is:maximum of $n$ and $d$ $n +d$$nd$$nd/2$
User Avatar
7 votes
2 answers
24
ISRO2007-62
Let $X$ be the adjacency matrix of a graph $G$ with no self loops. The entries along the principal diagonal of $X$ are all zeros all ones both zeros and ones different
Let $X$ be the adjacency matrix of a graph $G$ with no self loops. The entries along the principal diagonal of $X$ areall zerosall onesboth zeros and onesdifferent
User Avatar
10 votes
5 answers
25
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
2 votes
3 answers
26
N cube Graph
In N-cube graph we have no. of vertices = $2^N$ and no. of edges = $N*2^{N-1}$ Can anyone explain how we get this no. of edges?
In N-cube graph we have no. of vertices = $2^N$ and no. of edges = $N*2^{N-1}$Can anyone explain how we get this no. of edges?
User Avatar
28 votes
6 answers
28
GATE CSE 2020 | Question: 52
Graph $G$ is obtained by adding vertex $s$ to $K_{3,4}$ and making $s$ adjacent to every vertex of $K_{3,4}$. The minimum number of colours required to edge-colour $G$ is _______
Graph $G$ is obtained by adding vertex $s$ to $K_{3,4}$ and making $s$ adjacent to every vertex of $K_{3,4}$. The minimum number of colours required to edge-colour $G$ is...
User Avatar
To see more, click for all the questions in this category.