The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
Facebook Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
Recent questions and answers in Graph Theory
+15
votes
9
answers
1
GATE201830
Let $G$ be a simple undirected graph. Let $T_D$ be a depth first search tree of $G$. Let $T_B$ be a breadth first search tree of $G$. Consider the following statements. No edge of $G$ is a cross edge with respect to $T_D$. (A cross edge in $G$ is between ... then $\mid ij \mid =1$. Which of the statements above must necessarily be true? I only II only Both I and II Neither I nor II
answered
19 hours
ago
in
Graph Theory
by
Shailendra_
(
449
points)

5.4k
views
gate2018
graphtheory
graphsearch
normal
+4
votes
3
answers
2
GATE201938
Let $G$ be any connected, weighted, undirected graph. $G$ has a unique minimum spanning tree, if no two edges of $G$ have the same weight. $G$ has a unique minimum spanning tree, if, for every cut of $G$, there is a unique minimumweight edge crossing the cut. Which of the following statements is/are TRUE? I only II only Both I and II Neither I nor II
answered
1 day
ago
in
Graph Theory
by
manikantsharma
(
411
points)

2.9k
views
gate2019
engineeringmathematics
discretemathematics
graphtheory
graphconnectivity
+1
vote
1
answer
3
Difference between DAG and Multistage graph
I have trouble understanding the difference between DAG and Multistage graph. I know what each of them is But I think that a multistage graph is also a DAG. Are multistage graphs a special kind of DAG?
answered
2 days
ago
in
Graph Theory
by
mohithjagalmohanan
(
15
points)

72
views
graphtheory
graphalgorithms
graphconnectivity
multistagegraph
directedacyclicgraph
dag
+2
votes
2
answers
4
CMI2018A4
Let $G=(V, E)$ be an undirected simple graph, and $s$ be a designated vertex in $G.$ For each $v\in V,$ let $d(v)$ be the length of a shortest path between $s$ and $v.$ For an edge $(u,v)$ in $G,$ what can not be the value of $d(u)d(v)?$ $2$ $1$ $0$ $1$
answered
6 days
ago
in
Graph Theory
by
SPodder
(
11
points)

19
views
cmi2018
graphtheory
undirectedgraph
simplegraph
shortestpath
+1
vote
1
answer
5
CMI2016A9
ScamTel has won a state government contract to connect $17$ cities by highspeed fibre optic links. Each link will connect a pair of cities so that the entire network is connectedthere is a path from each city to every other city. The contract requires the network to remain ... $34$ $32$ $17$ $16$
answered
Nov 9
in
Graph Theory
by
`JEET
Boss
(
11.3k
points)

52
views
cmi2016
graphtheory
graphconnectivity
path
+26
votes
4
answers
6
GATE200673
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}$
answered
Oct 22
in
Graph Theory
by
shaktisingh
(
303
points)

2.5k
views
gate2006
graphtheory
normal
graphconnectivity
+33
votes
8
answers
7
GATE19941.6, ISRO200829
The number of distinct simple graphs with up to three nodes is $15$ $10$ $7$ $9$
answered
Oct 19
in
Graph Theory
by
Saurabh666
(
411
points)

9.5k
views
gate1994
graphtheory
permutationandcombination
normal
isro2008
counting
+2
votes
3
answers
8
Made easy
What is the chromatic number of following graphs? 1) 2)
answered
Oct 16
in
Graph Theory
by
chirudeepnamini
Active
(
2.5k
points)

175
views
graphcoloring
discrete
engineeringmathematics
+1
vote
1
answer
9
graph Theory
Consider an undirected graph G where selfloops are not allowed. The vertex set of G is {(i,j):1<=i<=12,1<=j<=12}. There is an edge between (a, b) and (c, d) if ac<=1 and bd<=1. The number of edges in this graph is __________.
answered
Oct 1
in
Graph Theory
by
Mac2
(
11
points)

122
views
discretemathematics
graphtheory
+31
votes
3
answers
10
GATE20012.15
How many undirected graphs (not necessarily connected) can be constructed out of a given set $V=\{v_1, v_2, \dots v_n\}$ of $n$ vertices? $\frac{n(n1)} {2}$ $2^n$ $n!$ $2^\frac{n(n1)} {2} $
answered
Sep 26
in
Graph Theory
by
HeartBleed
Junior
(
767
points)

4k
views
gate2001
graphtheory
normal
counting
+35
votes
9
answers
11
GATE2014351
If $G$ is the forest with $n$ vertices and $k$ connected components, how many edges does $G$ have? $\left\lfloor\frac {n}{k}\right\rfloor$ $\left\lceil \frac{n}{k} \right\rceil$ $nk$ $nk+1$
answered
Sep 24
in
Graph Theory
by
HeartBleed
Junior
(
767
points)

4.5k
views
gate20143
graphtheory
graphconnectivity
normal
+1
vote
1
answer
12
CMI2018B3
Let $G$ be a simple graph on $n$ vertices. Prove that if $G$ has more than $\binom{n1}{2}$ edges then $G$ is connected. For every $n>2$, find a graph $G_{n}$ which has exactly $n$ vertices and $\binom{n1}{2}$ edges, and is not connected.
answered
Sep 18
in
Graph Theory
by
prashant jha 1
Loyal
(
5.7k
points)

20
views
cmi2018
graphtheory
simplegraph
graphconnectivity
descriptive
+3
votes
2
answers
13
UGCNETJune2019II5
For which values of $m$ and $n$ does the complete bipartite graph $k_{m,n}$ have a Hamiltonian circuit ? $m\neq n,\ \ m,n \geq 2$ $m\neq n,\ \ m,n \geq 3$ $m=n,\ \ m,n \geq 2$ $m= n,\ \ m,n \geq 3$
answered
Sep 17
in
Graph Theory
by
Raghava45
(
349
points)

220
views
ugcnetjune2019ii
graphtheory
0
votes
1
answer
14
CMI2019B4
Consider the assertion: Any connected undirected graph $G$ with at least two vertices contains a vertex $v$ such that deleting $v$ from $G$ results in a connected graph. Either give a proof of the assertion, or give a counterexample (thereby disproving the assertion).
answered
Sep 17
in
Graph Theory
by
`JEET
Boss
(
11.3k
points)

15
views
cmi2019
graphconnectivity
undirectedgraph
0
votes
1
answer
15
CMI2018A9
Your college has sent a contingent to take part in a cultural festival at a neighbouring institution. Several team events are part of the programme. Each event takes place through the day with many elimination rounds. Your contingent is multitalented ... : Find a maximum length simple cycle Find a maximum size independent set Find a maximum matching Find a maximal connected component
answered
Sep 14
in
Graph Theory
by
`JEET
Boss
(
11.3k
points)

15
views
cmi2018
graphtheory
graphconnectivity
graphmatching
independentset
descriptive
+13
votes
3
answers
16
ISI Entrance Exam MTech (CS)
Consider all possible trees with $n$ nodes. Let $k$ be the number of nodes with degree greater than $1$ in a given tree. What is the maximum possible value of $k$?
answered
Sep 14
in
Graph Theory
by
rohith1001
Junior
(
871
points)

944
views
isi2016
graphtheory
trees
descriptive
+1
vote
0
answers
17
CMI2018B5
Let $G=(V,E)$ be an undirected graph and $V=\{1,2,\cdots,n\}.$ The input graph is given to you by a $01$ matrix $A$ of size $n\times n$ as follows. For any $1\leq i,j\leq n,$ the entry $A[i,j]=1$ if and only if ... any two vertices are connected to each other by paths. Give a simple algorithm to find the number of connected components in $G.$ Analyze the time taken by your procedure.
asked
Sep 13
in
Graph Theory
by
gatecse
Boss
(
16.6k
points)

14
views
cmi2018
graphtheory
undirectedgraph
graphconnectivity
connectedcomponents
descriptive
+5
votes
2
answers
18
MadeEasy Test Series 2018: Graph Theory  Graph Coloring
answer given is 4. Please provide a detailed solution.
answered
Sep 3
in
Graph Theory
by
Rishav_Bhatt
(
145
points)

164
views
graphtheory
graphcoloring
madeeasytestseries
madeeasytestseries2018
0
votes
1
answer
19
CUTSET
answered
Sep 1
in
Graph Theory
by
Devvrat Tyagi
(
159
points)

68
views
+27
votes
6
answers
20
GATE2014251
A cycle on $n$ vertices is isomorphic to its complement. The value of $n$ is _____.
answered
Aug 21
in
Graph Theory
by
King Suleiman
Junior
(
917
points)

3.8k
views
gate20142
graphtheory
numericalanswers
normal
graphisomorphism
nongate
+1
vote
2
answers
21
Graph Connectivity
Consider the given statements S1: In a simple graph G with 6 vertices, if degree of each vertex is 2, then Euler circuit exists in G. S2:In a simple graph G, if degree of each vertex is 3 then the graph G is connected. Which of the following is/are true?
answered
Aug 5
in
Graph Theory
by
IamDRD
(
51
points)

226
views
graphtheory
eulergraph
graphconnectivity
+1
vote
2
answers
22
#ACE_ACADEMY_DISCRETE_MATHS_BOOKLET.
Which of the following is not true? (a) Number of edgedisjoint Hamiltonian cycles in $K_7$ is $3$ (b) If $G$ is a simple graph with $6$ vertices and the degree of each vertex is at least $3$, then the Hamiltonian cycle exists in ... simple graph with $5$ vertices and $7$ edges, then the Hamiltonian cycle exists in $G$ Please help me understand all the options.
answered
Aug 1
in
Graph Theory
by
Raghava45
(
349
points)

111
views
discretemathematics
graphtheory
+2
votes
3
answers
23
UGCNETJune2015II5
Consider a Hamiltonian Graph(G) with no loops and parallel edges. Which of the following is true with respect to this graph (G)? deg (v) $\geq$ n/2 for each vertex of G $\mid E(G) \mid \geq $1/2 (n1)(n2)+2 edges deg(v) + deg(w) $\geq$ n fr every v and $\omega$ not connected by an edge a and b b and c a and c a, b, and c
answered
Aug 1
in
Graph Theory
by
tripu
(
11
points)

1.9k
views
ugcnetjune2015ii
discretemathematics
graphtheory
+1
vote
1
answer
24
UGCNETJune2019II69
Consider the following properties with respect to a flow network $G=(V,E)$ in which a flow is a realvalued function $f:V \times V \rightarrow R$: $P_1$: For all $u, v, \in V, \: f(u,v)=f(v,u)$ $P_2$: $\underset{v \in V}{\Sigma} f(u,v)=0$ for all $u \in V$ Which one of the following is/are correct? Only $P_1$ Only $P_2$ Both $P_1$ and $P_2$ Neither $P_1$ nor $P_2$
answered
Jul 29
in
Graph Theory
by
abhinav kumar
(
75
points)

94
views
ugcnetjune2019ii
flownetwork
+2
votes
3
answers
25
ACE ACADEMY BOOKLET QUESTION
Let $G$ $=$ $(V, E)$ be a simple nonempty connected undirected graph, in which every vertex has degree 4. For any partition $V$ into two nonempty and nonoverlapping subsets $S$ and $T$. Which of the following is true? There are at least two edges that ... $S$ and one end point in $T$ There are exactly one edge that have one end point in $S$ and one end point in $T$
answered
Jul 26
in
Graph Theory
by
gvjha3
(
11
points)

124
views
+1
vote
1
answer
26
graph theory(basic doubt)
Q.1)How many nonisomorphic simple graph are there with 6 vertices and 4 edges??
answered
Jul 24
in
Graph Theory
by
gorya506
(
201
points)

62
views
+37
votes
7
answers
27
GATE200340
A graph $G=(V,E)$ satisfies $\mid E \mid \leq 3 \mid V \mid  6$. The mindegree of $G$ is defined as $\min_{v\in V}\left\{ \text{degree }(v)\right \}$. Therefore, mindegree of $G$ cannot be $3$ $4$ $5$ $6$
answered
Jul 14
in
Graph Theory
by
PRANAV M
(
257
points)

3.7k
views
gate2003
graphtheory
normal
degreeofgraph
+41
votes
3
answers
28
GATE200479
How many graphs on $n$ labeled vertices exist which have at least $\frac{(n^2  3n)}{ 2}$ edges ? $^{\left(\frac{n^2n}{2}\right)}C_{\left(\frac{n^23n} {2}\right)}$ $^{{\large\sum\limits_{k=0}^{\left (\frac{n^23n}{2} \right )}}.\left(n^2n\right)}C_k\\$ $^{\left(\frac{n^2n}{2}\right)}C_n\\$ $^{{\large\sum\limits_{k=0}^n}.\left(\frac{n^2n}{2}\right)}C_k$
answered
Jul 5
in
Graph Theory
by
pritishc
(
437
points)

4.3k
views
gate2004
graphtheory
permutationandcombination
normal
counting
0
votes
1
answer
29
planar graph
Is this a planar graph ?
answered
Jul 4
in
Graph Theory
by
Peyush
(
11
points)

99
views
+3
votes
1
answer
30
UGCNETJune2019II4
Suppose that a connected planar graph has six vertices, each of degree four. Into how many regions is the plane divided by a planar representation of this graph? $6$ $8$ $12$ $20$
answered
Jul 3
in
Graph Theory
by
Satbir
Boss
(
20.7k
points)

227
views
ugcnetjune2019ii
graphplanarity
handshakingtheorem
+2
votes
1
answer
31
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?
answered
Jun 21
in
Graph Theory
by
Satbir
Boss
(
20.7k
points)

309
views
graphtheory
graphcoloring
permutationandcombination
0
votes
1
answer
32
Planar Graph
Can minimum degree of a planar graph be $5$? Give some example
answered
Jun 21
in
Graph Theory
by
Satbir
Boss
(
20.7k
points)

259
views
graphtheory
graphplanarity
+1
vote
1
answer
33
Doubt
How many distinct unlabeled graphs are there with 4 vertices and 3 edges?
answered
Jun 13
in
Graph Theory
by
Gyanu
Active
(
1.9k
points)

75
views
0
votes
1
answer
34
Zeal Test Series 2019: Graph Theory  Graph Connectivity
answered
Jun 12
in
Graph Theory
by
Gyanu
Active
(
1.9k
points)

112
views
zeal
graphtheory
graphconnectivity
zeal2019
+2
votes
3
answers
35
Degree of vertices
Consider an undirected graph with $n$ vertices, vertex $1$ has degree $1$,while each vertex $2,3,.............,n1$ has degree $4$.The degree of vertex $n$ is unknown. Which of the following statement must be true? Vertex $n$ has degree $1$ Graph is connected There is a path from vertex $1$ to vertex $n$ Spanning tree will include edge connecting vertex $1$ and vertex $n$
answered
Jun 12
in
Graph Theory
by
Sainath Mandavilli
(
23
points)

133
views
discretemathematics
graphtheory
0
votes
2
answers
36
ACE Workbook:
ACE Workbook: Q) Let G be a simple graph(connected) with minimum number of edges. If G has n vertices with degree1,2 vertices of degree 2, 4 vertices of degree 3 and 3 vertices of degree4, then value of n is ? Can anyone give the answer and how to approach these problems. Thanks in advance.
answered
Jun 12
in
Graph Theory
by
Akanksha Agrawal
(
129
points)

94
views
graphtheory
+1
vote
1
answer
37
TIFR2019B12
Let $G=(V,E)$ be a directed graph with $n(\geq 2)$ vertices, including a special vertex $r$. Each edge $e \in E$ has a strictly positive edge weight $w(e)$. An arborescence in $G$ rooted at $r$ is a subgraph $H$ of $G$ in which every ... $w^*$ is less than the weight of the minimum weight directed Hamiltonian cycle in $G$, when $G$ has a directed Hamiltonian cycle
answered
Jun 8
in
Graph Theory
by
Arjun
Veteran
(
423k
points)

314
views
tifr2019
graphconnectivity
graphtheory
difficult
+2
votes
1
answer
38
GATE19879d
Specify an adjacencylists representation of the undirected graph given above.
answered
Jun 5
in
Graph Theory
by
Satbir
Boss
(
20.7k
points)

346
views
gate1987
graphtheory
easy
graphconnectivity
descriptive
0
votes
2
answers
39
#GRAPH THEORY
A simple regular graph n vertices and 24 edges, find all possible values of n.
answered
Jun 4
in
Graph Theory
by
rballiwal
Active
(
1.2k
points)

107
views
graphtheory
0
votes
1
answer
40
self doubt
What is the general formula for number of simple graph having n unlabelled vertices ??
answered
Jun 4
in
Graph Theory
by
rballiwal
Active
(
1.2k
points)

56
views
simplegraph
To see more, click for all the
questions in this category
.
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
OFFICIAL GATE MOCK TEST RELEASED
IIITH: Winter Research Admissions 2019 (For Spring 2020)
TIFR and JEST exam
Minimal Deterministic Finite Automata
To be aware of fake GATE test series
All categories
General Aptitude
1.9k
Engineering Mathematics
7.5k
Discrete Mathematics
5.2k
Mathematical Logic
2.1k
Set Theory & Algebra
1.4k
Combinatory
902
Graph Theory
816
Probability
1k
Linear Algebra
710
Calculus
563
Digital Logic
2.9k
Programming and DS
4.9k
Algorithms
4.3k
Theory of Computation
6.2k
Compiler Design
2.1k
Operating System
4.5k
Databases
4.1k
CO and Architecture
3.4k
Computer Networks
4.1k
Non GATE
1.4k
Others
1.6k
Admissions
595
Exam Queries
576
Tier 1 Placement Questions
23
Job Queries
72
Projects
17
Follow @csegate
Recent questions and answers in Graph Theory
Recent Blog Comments
still it's usefull for practice purpose and...
@Satbir Its a valuable info..Thanks
It is the 2019 question paper given as a mock...
Favorite is not working for blogs.. In favorites...
Favourite option does work. But list options...
50,650
questions
56,185
answers
193,937
comments
94,684
users