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

Recent questions in Graph Theory

#1
237
views
1 answers
0 votes
isi mtech cse 2024 admission test
For any undirected connected graph \( G \), let \( \chi(G) \) be the minimum number of colours needed to colour all the vertices of \( G \) in such a way that no two adjacent ... i}, v_{i+1}\right) \) is an edge for \( 1 \leq i \leq k \)
User Avatar
#2
103
views
0 answers
0 votes
ISI PCB 2023 Q3
User Avatar
#3
233
views
1 answers
0 votes
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$.
User Avatar
#4
208
views
1 answers
0 votes
Practice Material Question
If G is a connected graph with 6 vertices and maximum number of edges, then which of the following is true ? (a) Euler path exists, but Euler circuit does not exist ... in G.(c) Euler circuit does not exists in G(d) G is not traversable.
User Avatar
#5
3.6k
views
2 answers
3 votes
GATE CSE 2024 | Set 2 | Question: 7
Let $\text{A}$ be the adjacency matrix of a simple undirected graph $\text{G}$. Suppose $\text{A}$ is its own inverse. Which one of the following ... perfect matching$\text{G}$ is a complete graphThere is no such graph $\text{G}$
User Avatar
#6
2.5k
views
1 answers
1 votes
GATE CSE 2024 | Set 2 | Question: 41
Let $\text{G}$ be an undirected connected graph in which every edge has a positive integer weight. Suppose that every spanning tree in $\text{G}$ has even weight. ... have even weight $\text{OR}$ all edges in $\text{C}$ have odd weight
User Avatar
#7
2.6k
views
4 answers
2 votes
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 __________.
User Avatar
#8
2.6k
views
2 answers
4 votes
GATE CSE 2024 | Set 1 | Question: 24
The number of spanning trees in a complete graph of $4$ vertices labelled $\text{A, B, C,}$ and $\text{D}$ is _________.
User Avatar
#9
2.7k
views
2 answers
2 votes
GATE CSE 2024 | Set 1 | Question: 41
The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. Let $G$ be any graph with $n$ vertices and chromatic number $k$ ... $k(k-1) / 2$ edges$G$ contains a vertex of degree at least $k$
User Avatar
#10
293
views
0 answers
1 votes
Gate 2016
The minimum number of colours that is sufficient to vertex-colour any planar graph is ________.I am confused with the question's language.please correct me if I have a ... answer not to be less than 4. What does the word "any" means here?
User Avatar
#11
829
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 , ... the following can be the degree of the last vertex? (Select all that are possible)0348
User Avatar
#12
673
views
1 answers
7 votes
GO Classes Test Series 2024 | Mock GATE | Test 14 | Question: 57
A strongly connected component $(\mathrm{SCC})$ of a directed graph $\mathrm{G}=(\mathrm{V}, \mathrm{E})$ is a maximal set of vertices such that any two vertices in ... acyclic graph $G^{\prime}$ be $A, B$ respectively, then what is $A+B?$
User Avatar
#13
170
views
0 answers
1 votes
Memory Based GATE DA 2024 | Question: 64
Minimum Number of colors in concentric circles.
User Avatar
#14
212
views
1 answers
1 votes
#self doubt
In the above figure, how many topological sorts are possible,I tried the following method,if we include 5 _ _ _ _ _ for 5 space 5c3 for (2,3,1 ... is coming ? https://www.geeksforgeeks.org/all-topological-sorts-of-a-directed-acyclic-graph/
User Avatar
#15
556
views
1 answers
3 votes
GO Classes Test Series 2024 | Mock GATE | Test 13 | Question: 63
For an undirected graph $G$, let $\overline{G}$ refer to the complement (a graph on the same vertex set as $G$, with $(i, j)$ as an edge in $\overline{G}$ if and ... v).(i) is equivalent to (ii) and (iv).(i) is equivalent to (ii) and (v)
User Avatar
#16
783
views
1 answers
4 votes
GO Classes Test Series 2024 | Mock GATE | Test 12 | Question: 46
Assume the following graph is a labeled graph i.e. every vertex has a unique label.In how many ways can we color the following labeled graph $\mathrm{G}$ with ... such that no two adjacent vertices are assigned the same color?
User Avatar
#17
555
views
1 answers
3 votes
GO Classes Test Series 2024 | Mock GATE | Test 11 | Question: 11
The figure above shows an undirected graph with six vertices. Enough edges are to be deleted from the graph in order to leave a spanning tree, which is a ... having the same six vertices and no cycles. How many edges must be deleted?
User Avatar
#18
160
views
0 answers
0 votes
Consider a weighted undirected graph with positive edge weights and let (u, v) be an [2] edge in the graph. It is known that the shortest path from source vertex r to u has weight 53 and shortest path from r to v has weight 65. Which statement is always true?
Consider a weighted undirected graph with positive edge weights and let (u, v) be an [2]edge in the graph. It is known that the shortest path from source ... and shortest path from r to v has weight 65. Which statement is always true?
User Avatar
#19
238
views
1 answers
0 votes
ISRO 2024
Maximum number of Simple graphs possible with $n$ vertices$2^{n(n-1)/2}$2^{(n-1)/2}$2^{n(n+1)/2}$2^{n(n+1)}$
User Avatar
#20
347
views
1 answers
0 votes
ISRO 2024
If there are five faces and nine vertices in an undirected planar graph, then number of edges is14612None of the above
User Avatar
Page: