Login
Register
@
Dark Mode
Profile
Edit my Profile
Messages
My favorites
Register
Activity
Q&A
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous Years
Blogs
New Blog
Exams
Dark Mode
Recent questions and answers in Graph Theory
0
votes
0
answers
1
#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?
Gate Shark
asked
in
Graph Theory
Feb 17
by
Gate Shark
71
views
graph-theory
4
votes
2
answers
2
GATE CSE 2023 | Question: 45
Let $G$ be a simple, finite, undirected graph with vertex set $\left\{v_{1}, \ldots, v_{n}\right\}$. Let $\Delta(G)$ denote the maximum degree of $G$ and let $\mathbb{N}=\{1,2, \ldots\}$ denote the set of all possible colors. Color the vertices ... $\Delta(G)$. The number of colors used is equal to the chromatic number of $G$.
Deepak Poonia
answered
in
Graph Theory
Feb 16
by
Deepak Poonia
2.1k
views
gatecse-2023
graph-theory
graph-coloring
multiple-selects
2-marks
13
votes
4
answers
3
GATE CSE 2022 | Question: 42
Which of the properties hold for the adjacency matrix $A$ of a simple undirected unweighted graph having $n$ vertices? The diagonal entries of $A^{2}$ ... . If there is at least a $1$ in each of $A\text{'s}$ rows and columns, then the graph must be connected.
Deepak Poonia
answered
in
Graph Theory
Jan 28
by
Deepak Poonia
3.4k
views
gatecse-2022
graph-theory
graph-connectivity
multiple-selects
2-marks
1
vote
0
answers
4
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?
Sahil_Lather
asked
in
Graph Theory
Jan 27
by
Sahil_Lather
120
views
graph-theory
testbook-test-series
graph-planarity
0
votes
0
answers
5
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
Sahil_Lather
asked
in
Graph Theory
Jan 27
by
Sahil_Lather
86
views
graph-theory
bipartite-graph
testbook-test-series
0
votes
0
answers
6
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
Sahil_Lather
asked
in
Graph Theory
Jan 27
by
Sahil_Lather
48
views
graph-theory
lattice
42
votes
7
answers
7
GATE CSE 2006 | Question: 73
The $2^n$ vertices of a graph $G$ corresponds to all subsets of a set of size $n$, for $n \geq 6$. Two vertices of $G$ are adjacent if and only if the corresponding sets intersect in exactly two elements. The number of connected components in $G$ is: $n$ $n + 2$ $2^{\frac{n}{2}}$ $\frac{2^{n}}{n}$
sameer_hack
answered
in
Graph Theory
Jan 14
by
sameer_hack
6.7k
views
gatecse-2006
graph-theory
normal
graph-connectivity
4
votes
2
answers
8
TIFR CSE 2022 | Part B | Question: 2
Let $G=(V, E)$ be an undirected simple graph. A subset $M \subseteq E$ is a matching in $G$ if distinct edges in $M$ do not share a vertex. A matching is maximal if no strict superset of $M$ is a matching. How many maximal matchings does the following graph have? $1$ $2$ $3$ $4$ $5$
GNANESWARA SAI
answered
in
Graph Theory
Jan 6
by
GNANESWARA SAI
311
views
tifr2022
graph-theory
graph-matching
0
votes
1
answer
9
Made Easy Test Series | Discrete Maths | POSET | Chain length
50 51 52 53
Souvik33
answered
in
Graph Theory
Jan 5
by
Souvik33
152
views
made-easy-test-series
discrete-mathematics
1
vote
4
answers
10
CMI2013-B-03
A simple graph is one in which there are no self loops and each pair of distinct vertices is connected by at most one edge. Show that any finite simple graph has at least two vertices with the same degree.
GNANESWARA SAI
answered
in
Graph Theory
Jan 5
by
GNANESWARA SAI
656
views
cmi2013
descriptive
graph-theory
graph-connectivity
60
votes
8
answers
11
GATE IT 2006 | Question: 25
Consider the undirected graph $G$ defined as follows. The vertices of $G$ are bit strings of length $n$. We have an edge between vertex $u$ and vertex $v$ if and only if $u$ and $v$ differ in exactly one bit position (in other words, $v$ can be obtained from $u$ by ... $\left(\frac{1}{n}\right)$ $\left(\frac{2}{n}\right)$ $\left(\frac{3}{n}\right)$
GNANESWARA SAI
answered
in
Graph Theory
Jan 5
by
GNANESWARA SAI
10.5k
views
gateit-2006
graph-theory
graph-coloring
normal
3
votes
0
answers
12
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 ?
Kabir5454
asked
in
Graph Theory
Jan 2
by
Kabir5454
167
views
zeal
graph-theory
discrete-mathematics
graph-coloring
numerical-answers
1
vote
0
answers
13
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]\]
admin
asked
in
Graph Theory
Dec 15, 2022
by
admin
64
views
drdocse-2022-paper1
graph-theory
bipartite-graph
graph-matching
4-marks
descriptive
1
vote
0
answers
14
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?
admin
asked
in
Graph Theory
Dec 15, 2022
by
admin
73
views
drdocse-2022-paper1
graph-theory
graph-coloring
4-marks
descriptive
1
vote
0
answers
15
DRDO CSE 2022 Paper 1 | Question: 11
Consider the following graph. Find closeness centrality of $\text{‘A’}$ node.
admin
asked
in
Graph Theory
Dec 15, 2022
by
admin
70
views
drdocse-2022-paper1
graph-theory
graph-connectivity
5-marks
descriptive
1
vote
0
answers
16
DRDO CSE 2022 Paper 1 | Question: 13
Consider the following graph. Which nodes form the cliques of size $3?$
admin
asked
in
Graph Theory
Dec 15, 2022
by
admin
62
views
drdocse-2022-paper1
graph-theory
graph-connectivity
5-marks
descriptive
27
votes
9
answers
17
GATE CSE 2015 Set 1 | Question: 54
Let G be a connected planar graph with 10 vertices. If the number of edges on each face is three, then the number of edges in G is_______________.
rsansiya111
answered
in
Graph Theory
Dec 12, 2022
by
rsansiya111
20.7k
views
gatecse-2015-set1
graph-theory
graph-connectivity
normal
graph-planarity
numerical-answers
14
votes
5
answers
18
GATE CSE 2022 | Question: 20
Consider a simple undirected graph of $10$ vertices. If the graph is disconnected, then the maximum number of edges it can have is _______________ .
dutta18
answered
in
Graph Theory
Dec 1, 2022
by
dutta18
3.9k
views
gatecse-2022
numerical-answers
graph-theory
graph-connectivity
1-mark
1
vote
1
answer
19
TIFR CSE 2022 | Part B | Question: 14
Let $G$ be a directed graph (with no self-loops or parallel edges) with $n \geq 2$ vertices and $m$ edges. Consider the $n \times m$ incidence matrix $M$ of $G$, whose rows are indexed by the vertices of $G$ and the columns by the edges of $G$ ... . Then, what is the rank of $M?$ $m-1$ $m-n+1$ $\lceil m / 2\rceil$ $n-1$ $\lceil n / 2\rceil$
Kunalbag7
answered
in
Graph Theory
Nov 10, 2022
by
Kunalbag7
156
views
tifr2022
graph-theory
graph-connectivity
rank-of-matrix
3
votes
1
answer
20
TIFR CSE 2022 | Part B | Question: 6
We are given a graph $G$ along with a matching $M$ and a vertex cover $C$ in it such that $|M|=|C|$. Consider the following statements: $M$ is a maximum matching in $G$. $C$ is a minimum vertex cover in $G$. $G$ is a bipartite graph. Which of ... $(1)$ and $(2)$ are correct All the three statements $(1), (2),$ and $(3)$ are correct
Deepak Poonia
answered
in
Graph Theory
Nov 9, 2022
by
Deepak Poonia
361
views
tifr2022
graph-theory
graph-matching
0
votes
2
answers
21
Virtual Gate
A complete graph on n vertices is an undirected graph in which every pair of distinct vertices is connected by an edge. A simple path in a graph is one in which no vertex is repeated. Let G be a complete graph on 10 vertices. Let u, v, w be three distinct vertices in G. How many simple paths are there from u to v going through w?
Purple _ rain
answered
in
Graph Theory
Oct 16, 2022
by
Purple _ rain
498
views
discrete-mathematics
graph-theory
test-series
4
votes
2
answers
22
Graph Coloring
How many ways are there to color this graph from any $4$ of the following colors : Violet, Indigo, Blue, Green, Yellow, Orange and Red ? There is a condition that adjacent vertices should not be of the same color I am getting $1680$. Is it correct?
DAWID15
answered
in
Graph Theory
Oct 13, 2022
by
DAWID15
1.7k
views
graph-theory
graph-coloring
combinatory
2
votes
2
answers
23
Seld doubt DM
Consider a tree T with n vertices and (n – 1) edges. We define a term called cyclic cardinality of a tree (T) as the number of cycles created when any two vertices of T are joined by an edge. Given a tree with 10 vertices, what is the cyclic cardinality of this tree?
Kd55
answered
in
Graph Theory
Oct 10, 2022
by
Kd55
837
views
2
votes
4
answers
24
GATE Overflow | Mock GATE | Test 1 | Question: 34
Let $G$ be a graph of order $n$ in which every vertex has degree equal to $d$. How large must $d$ be in order to guarantee that $G$ is connected? $\frac{n}{2}$ $\lceil (n-1)/2 \rceil$ $\lfloor (n+1)/2 \rfloor$ $(n-1)/2$
Kd55
answered
in
Graph Theory
Oct 1, 2022
by
Kd55
1.4k
views
go-mockgate-1
discrete-mathematics
graph-theory
graph-connectivity
1
vote
0
answers
25
TIFR CSE 2022 | Part B | Question: 12
Given an undirected graph $G$, an ordering $\sigma$ of its vertices is called a perfect ordering if for every vertex $v$, the neighbours of $v$ which precede $v$ in $\sigma$ form a clique in $G$. Recall that given an undirected ... SPECIAL-COLOURING are in $\mathrm{P}$ Neither of SPECIAL-CLiQUE and SPECIAL-COLOURING is in $\mathrm{P},$ but both are decidable
admin
asked
in
Graph Theory
Sep 1, 2022
by
admin
139
views
tifr2022
graph-theory
graph-coloring
p-np-npc-nph
57
votes
8
answers
26
GATE CSE 2013 | Question: 26
The line graph $L(G)$ of a simple graph $G$ is defined as follows: There is exactly one vertex $v(e)$ in $L(G)$ for each edge $e$ in $G$. For any two edges $e$ and $e'$ in $G$, $L(G)$ has an edge between $v(e)$ and $v(e')$, if and only if $e$ ... of a planar graph is planar. (S) The line graph of a tree is a tree. $P$ only $P$ and $R$ only $R$ only $P, Q$ and $S$ only
Jyotish Ranjan
answered
in
Graph Theory
Aug 7, 2022
by
Jyotish Ranjan
15.5k
views
gatecse-2013
graph-theory
normal
graph-connectivity
4
votes
2
answers
27
GO Classes Scholarship 2023 | Test | Question: 9
Consider the following graph $\text{G:}$ Let $\text{M, C, I, S, B, E}$ be the Matching number, chromatic number, independence number, Clique number, Vertex cover number, and edge cover number, respectively of $\text{G}.$ What is $\text{M+C+I+S+B+E}?$
Kabir5454
answered
in
Graph Theory
Aug 7, 2022
by
Kabir5454
410
views
goclasses-scholarship-test1
numerical-answers
goclasses
graph-theory
graph-connectivity
vertex-cover
2-marks
3
votes
1
answer
28
GO Classes Scholarship 2023 | Test | Question: 8
In a directed graph $\mathrm{G}=(\mathrm{V}, \mathrm{E})$, two nodes $u$ and $v$ are strongly connected if and only if they are mutually reachable i.e. there is a path from u to $v$ and a path from $v$ to $u$. ... connected components $\dots?$ can not increase can not decrease by more than $1$ can not decrease by more than $2$ may remain unchanged
GO Classes
answered
in
Graph Theory
Aug 7, 2022
by
GO Classes
386
views
goclasses-scholarship-test1
goclasses
graph-theory
graph-connectivity
multiple-selects
1-mark
3
votes
1
answer
29
GO Classes Scholarship 2023 | Test | Question: 10
For which of the following does there exist a graph satisfying the specified conditions? A tree with six vertices and six edges. A tree with three or more vertices, two vertices of degree one, and all the other vertices with degree three or ... with $10$ vertices and $8$ edges. A disconnected graph with $12$ vertices and $11$ edges and no cycle.
GO Classes
answered
in
Graph Theory
Aug 7, 2022
by
GO Classes
263
views
goclasses-scholarship-test1
goclasses
graph-theory
graph-connectivity
multiple-selects
2-marks
4
votes
1
answer
30
GO Classes Scholarship 2023 | Test | Question: 12
How many non-isomorphic simple undirected graphs are there, each with four vertices and without a cycle?
GO Classes
answered
in
Graph Theory
Aug 7, 2022
by
GO Classes
309
views
goclasses-scholarship-test1
numerical-answers
goclasses
graph-theory
graph-isomorphism
2-marks
66
votes
12
answers
31
GATE CSE 1994 | Question: 1.6, ISRO2008-29
The number of distinct simple graphs with up to three nodes is $15$ $10$ $7$ $9$
Cs_Gate_22
answered
in
Graph Theory
Aug 4, 2022
by
Cs_Gate_22
28.7k
views
gate1994
graph-theory
graph-connectivity
combinatory
normal
isro2008
counting
58
votes
4
answers
32
GATE CSE 2003 | Question: 8, ISRO2009-53
Let $\text{G}$ be an arbitrary graph with $n$ nodes and $k$ components. If a vertex is removed from $\text{G}$, the number of components in the resultant graph must necessarily lie down between $k$ and $n$ $k-1$ and $k+1$ $k-1$ and $n-1$ $k+1$ and $n-k$
Abhrajyoti00
answered
in
Graph Theory
Jul 23, 2022
by
Abhrajyoti00
12.3k
views
gatecse-2003
graph-theory
graph-connectivity
normal
isro2009
0
votes
1
answer
33
Self Doubt - Planarity of Complete Bipartite Graph
How to determine for which m, n the complete bipartite graph $Km,n$ is planar? I am getting two answers from two sources:- A complete bipartite graph $Kmn$ is planar if and only if m<3 or n>3. Source: https://www.javatpoint.com/ ... m ≤ 2 or n ≤ 2. Source: http://www.matthewkahle.org/download/file/fid/573 Need a proper proof of the solution.
Abhrajyoti00
asked
in
Graph Theory
Jul 21, 2022
by
Abhrajyoti00
253
views
graph-theory
bipartite-graph
discrete-mathematics
graph-planarity
0
votes
1
answer
34
Degree sequence of graph
Someone please solve it.
Overflow04
asked
in
Graph Theory
Jun 30, 2022
by
Overflow04
217
views
ace-test-series
degree-of-graph
0
votes
1
answer
35
Doubt:
Let “m” be the number of edges, “n” the number of vertices and “k” the number of connected components of a graph G. Prove that: $\left ( n-k \right )\leq m\leq \frac{\left ( n-k \right )\left ( n-k+1 \right )}{2}$ Why least number of edges are $\left ( n-k \right )$ and Why most number of edges are $\frac{\left ( n-k \right )\left ( n-k+1 \right )}{2}$ ? What is the idea behind this prove?
RKM
asked
in
Graph Theory
Jun 28, 2022
by
RKM
221
views
graph-connectivity
0
votes
0
answers
36
Introduction to Graph Theory Exercises
This is the problem snapshot
AngshukN
asked
in
Graph Theory
May 22, 2022
by
AngshukN
243
views
graph-theory
graph-connectivity
discrete-mathematics
0
votes
1
answer
37
What is the number of faces in a connected plane graph having 23 vertices, 30 edges?
What is the number of faces in a connected plane graph having 23 vertices, 30 edges?
R S BAGDA
asked
in
Graph Theory
Apr 27, 2022
by
R S BAGDA
154
views
graph-theory
12
votes
2
answers
38
GATE CSE 2022 | Question: 27
Consider a simple undirected unweighted graph with at least three vertices. If $\textit{A}$ is the adjacency matrix of the graph, then the number of $3–$cycles in the graph is given by the trace of $\textit{A}^{3}$ $\textit{A}^{3}$ divided by $2$ $\textit{A}^{3}$ divided by $3$ $\textit{A}^{3}$ divided by $6$
Arjun
asked
in
Graph Theory
Feb 15, 2022
by
Arjun
3.4k
views
gatecse-2022
graph-theory
graph-connectivity
2-marks
11
votes
2
answers
39
GATE CSE 2022 | Question: 40
The following simple undirected graph is referred to as the Peterson graph. Which of the following statements is/are $\text{TRUE}?$ The chromatic number of the graph is $3.$ The graph has a Hamiltonian path. The following graph is isomorphic to the Peterson ... $3.$ (A subset of vertices of a graph form an independent set if no two vertices of the subset are adjacent.)
Arjun
asked
in
Graph Theory
Feb 15, 2022
by
Arjun
3.7k
views
gatecse-2022
graph-theory
graph-isomorphism
multiple-selects
2-marks
hard
1
vote
0
answers
40
Made Easy Full length Test
Options Given were---- ADC ABC Both the above None of these According to me the answer should be {A,B,C,D} as this is the largest set and every node is capable to reach every other node.. but the answer given was option C so can anyone plz tell me whats the correct answer?
Sagar475
asked
in
Graph Theory
Jan 18, 2022
by
Sagar475
226
views
To see more, click for all the
questions in this category
.
Subscribe to GATE CSE 2023 Test Series
Subscribe to GO Classes for GATE CSE 2023
Quick search syntax
tags
tag:apple
author
user:martin
title
title:apple
content
content:apple
exclude
-tag:apple
force match
+apple
views
views:100
score
score:10
answers
answers:2
is accepted
isaccepted:true
is closed
isclosed:true
Recent Posts
BITSHD 2023
My journey from being a MSc student to AIR 239 in GATE CSE 2023 and qualified UGC-NET JRF.
NEEPCO Recruitment 2023
GATE CSE 2023 Results
IIIT Banglore MTech 2023-24
Subjects
All categories
General Aptitude
(2.5k)
Engineering Mathematics
(9.3k)
Discrete Mathematics
(6.5k)
Mathematical Logic
(2.2k)
Set Theory & Algebra
(1.7k)
Combinatory
(1.5k)
Graph Theory
(996)
Probability
(1.2k)
Linear Algebra
(909)
Calculus
(717)
Digital Logic
(3.3k)
Programming and DS
(5.9k)
Algorithms
(4.6k)
Theory of Computation
(6.7k)
Compiler Design
(2.3k)
Operating System
(5.0k)
Databases
(4.6k)
CO and Architecture
(3.8k)
Computer Networks
(4.7k)
Non GATE
(1.3k)
Others
(2.5k)
Admissions
(653)
Exam Queries
(845)
Tier 1 Placement Questions
(17)
Job Queries
(76)
Projects
(9)
Unknown Category
(866)
Recent questions and answers in Graph Theory
Recent Blog Comments
Please provide some tips about NET, since I want...
Amazing story to hear
Link added now:...
Sir can you please provide some good resources...
Where can we see the responses of the form filled?