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

Most answered questions in Graph Theory

0 votes
1 answer
481
Induction
Prove that the number of edges in a graph with exactly one triangle is at most \begin{align*} \frac{\left( n - 1 \right )^2}{4} + 2 \end{align*}
Prove that the number of edges in a graph with exactly one triangle is at most \begin{align*} \frac{\left( n - 1 \right )^2}{4} + 2\end{align*}
User Avatar
1 votes
1 answer
482
PGEE 2018
Consider Undirected Graph G having vertex V {A,B,C,D,E} and edge pair as E {AB BD BE AC CE CD} A) Given graph is disconnected B) Given graph is complete C) Given graph has vertex connectivity 2 D) Given graph has edge connectivity 1
Consider Undirected Graph Ghaving vertex V {A,B,C,D,E}and edge pair as E {AB BD BE AC CE CD}A) Given graph is disconnectedB) Given graph is completeC) Given graph has ver...
User Avatar
1 votes
1 answer
484
Narsingh Deo Problem 2-28
User Avatar
1 votes
1 answer
485
Graph Theory
Let G be a simple graph in which every vertex has degree 3. Prove that G decomposes into claws iff G is bipartite.
Let G be a simple graph in which every vertex has degree 3. Prove that G decomposes into claws iff G is bipartite.
User Avatar
0 votes
1 answer
486
#Graph Theory Any Simple way to prove this ?
A connected graph ‘G’ may have at most (n–2) cut vertices.
A connected graph ‘G’ may have at most (n–2) cut vertices.
User Avatar
1 votes
1 answer
487
Graph Book
The maximum number of edges in a n-node undirected graph WITH self-loops is?
The maximum number of edges in a n-node undirected graph WITH self-loops is?
User Avatar
0 votes
1 answer
490
related to gate previous year
can some give example where cardinality of min-cut will be < min-degree of the graph I found in question they have mentioned its <= , but i dont see any case where it is < https://gateoverflow.in/1504/gate1999_5
can some give example where cardinality of min-cut will be < min-degree of the graph I found in question they have mentioned its <= , but i dont see any case where it is ...
User Avatar
1 votes
1 answer
492
Graph theory
As a triangle graph is $2 -$ connected, thus for a given triangle graph, $r= 2( r_1\text{ and } r_2)$ , $k=2, e = 3, v=3$, but it still doesn't satisfy the equation, Can someone tell me where did I go wrong? Thanks
As a triangle graph is $2 -$ connected, thus for a given triangle graph, $r= 2( r_1\text{ and } r_2)$ , $k=2, e = 3, v=3$, but it still doesn't satisfy the equation, Can ...
User Avatar
0 votes
1 answer
493
Rosen (Graph)
Show that an edge in a simple graph is a cut edge if and only if this edge is not a part of any simple circuit in the graph.
Show that an edge in a simple graph is a cut edge if and only if this edge is not a part of any simple circuit in the graph.
User Avatar
0 votes
1 answer
494
Kenneth Rosen Edition 6th Exercise 8.4 Question 70 (Page No. 565 )
How much storage is needed to represent a simple graph with n vertices and m edges using. a) adjacency lists? b) an adjacency matrix? c) an incidence matrix?
How much storage is needed to represent a simple graph with n vertices and m edges using.a) adjacency lists?b) an adjacency matrix?c) an incidence matrix?
User Avatar
0 votes
1 answer
495
discrete maths
Consider the following statements: S1: Every cyclic group is Abelian group. S2: Every Abelian group is cyclic group. S3: Cyclic group of order 10 have 4 generators. Which of the following is true?
Consider the following statements:S1: Every cyclic group is Abelian group.S2: Every Abelian group is cyclic group.S3: Cyclic group of order 10 have 4 generators.Which of ...
User Avatar
0 votes
1 answer
496
Test series
Plz explain ??
Plz explain ??
User Avatar
1 votes
1 answer
498
Ace Test Series: Graph Theory - Matching
my answer is C but the answer given is A someone please explain
my answer is Cbut the answer given is Asomeone please explain
User Avatar
7 votes
1 answer
499
Number of minimum spanning trees
The number of distinct minimum spanning trees for the weighted graph shown below is ___________.
The number of distinct minimum spanning trees for the weighted graph shown below is ___________.
User Avatar
7 votes
1 answer
500
Strongly connected component
Find the no of strongly connected components for the below graph. $5$ $4$ $9$ $2$
Find the no of strongly connected components for the below graph.$5$$4$$9$$2$
User Avatar
Page: