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

Hot questions in Graph Theory

25 votes
8 answers
92
GATE IT 2004 | Question: 5
What is the maximum number of edges in an acyclic undirected graph with $n$ vertices? $n-1$ $n$ $n+1$ $2n-1$
What is the maximum number of edges in an acyclic undirected graph with $n$ vertices?$n-1$$n$$n+1$$2n-1$
User Avatar
0 votes
1 answer
94
Planar Graphs | Graph Theory | Selfdoubt
In a Connected Planar Bipartite Graph of order 10 atmost how many edges be present ?
In a Connected Planar Bipartite Graph of order 10 atmost how many edges be present ?
User Avatar
1 votes
1 answer
96
Self Made Question
Consider a connected undirected graph G with n vertices, where n > 4. Suppose that G has the property that every vertex has a degree of at least n/2, i.e., deg(v) ≥ n/2 for all vertices v in G. Prove that G must contain a cycle of length at most 3n/4.
Consider a connected undirected graph G with n vertices, where n 4. Suppose that G has the property that every vertex has a degree of at least n/2, i.e., deg(v) ≥ n/2 ...
User Avatar
0 votes
1 answer
99
Byju's graph theory coloring question
Graph G is obtained by adding vertex s to $K_{3,4}$ and making s adjacent to every vertex of $K_{3,4}$ . The find the minimum number of colours required ot edge-colour 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 find the minimum number of colours required ot edge-colour is ...
User Avatar
2 votes
0 answers
101
discrete mathematics
The maximum number of edges possible in a graph G with 9 vertices which is 3 colourable is equal to A 24 B 27 C 36 D None of the above
The maximum number of edges possible in a graph G with 9 vertices which is 3 colourable is equal toA 24B 27C 36D None of the above
User Avatar
17 votes
2 answers
102
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 not Both K4 and Q3 are planar Q3 is planar while K4 is not Neither K4 nor Q3 is planar
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
0 votes
0 answers
103
#Graphs #Self_Doubt #Connectivity
What is a biconnected componenet?Does it always include V-V’ where V’ represent the set of articulation points of a graph G?
What is a biconnected componenet?Does it always include V-V’ where V’ represent the set of articulation points of a graph G?
User Avatar
9 votes
1 answer
104
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
0 answers
105
TestBook graph theory question
If G is a simple planar connected graph with 5 vertices, how many edges in maximum can be there in the given graph?
If G is a simple planar connected graph with 5 vertices, how many edges in maximum can be there in the given graph?
User Avatar
0 votes
0 answers
106
TestBook graph theory questions
Let Gn be the complete bipartite graph K13, 17 then the chromatic number of G̅n is _____ (G̅n is complement of Gn and n = 30) A 13 B 17 C n(n−1)2−13×17 D n(n−1)2−2
Let Gn be the complete bipartite graph K13, 17 then the chromatic number of G̅n is _____ (G̅n is complement of Gn and n = 30)A13B17Cn(n−1)2−13×17Dn(n−1)2−2
User Avatar
0 votes
0 answers
107
TestBook Hasse Diagram question to find GLB
If [P(A); ⊆] is a lattice where A = {x, y} and P(A) is the power set then what is the sum of element in Greatest Lower Bound (GLB) set of given lattice? x + y x y 0
If [P(A); ⊆] is a lattice where A = {x, y} and P(A) is the power set then what is the sum of element in Greatest Lower Bound (GLB) set of given lattice?x + y xy0
User Avatar
3 votes
0 answers
108
DRDO CSE 2022 Paper 1 | Question: 9
Count the number of perfect matchings in the bipartite graph whose adjacency matrix $\text{A}$ is as follows. \[\left[\begin{array}{lll} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 1 & 1 \end{array}\right]\]
Count the number of perfect matchings in the bipartite graph whose adjacency matrix $\text{A}$ is as follows.\[\left[\begin{array}{lll}1 & 1 & 0 \\0 & 1 & 1 \\1 & 1 & 1\e...
User Avatar
38 votes
4 answers
109
GATE CSE 2005 | Question: 11
Let $G$ be a simple graph with $20$ vertices and $100$ edges. The size of the minimum vertex cover of G is $8$. Then, the size of the maximum independent set of $G$ is: $12$ $8$ less than $8$ more than $12$
Let $G$ be a simple graph with $20$ vertices and $100$ edges. The size of the minimum vertex cover of G is $8$. Then, the size of the maximum independent set of $G$ is:$1...
User Avatar
3 votes
0 answers
110
graph theory
Let $G=(V,E)$ where $V=\left \{ 1,2,3,4,.....,150\right \}$ and $(u,v) \in E$ if either $(u mod v) =0$ or $(v mod u)=0$.The Chromatic number of G is ?
Let $G=(V,E)$ where $V=\left \{ 1,2,3,4,.....,150\right \}$ and $(u,v) \in E$ if either $(u mod v) =0$ or $(v mod u)=0$.The Chromatic number of G is ?
User Avatar
Page: