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

Hot questions in Graph Theory

0 votes
1 answer
101
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
104
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
107
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
109
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
39 votes
4 answers
110
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
17 votes
2 answers
112
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
113
#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
114
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
115
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
116
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
117
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
118
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
3 votes
0 answers
119
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: