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
+48
votes
5
answers
1
GATE2007IT25
What is the largest integer $m$ such that every simple connected graph with $n$ vertices and $n$ edges contains at least $m$ different spanning trees ? $1$ $2$ $3$ $n$
answered
Jan 6
in
Graph Theory
by
endurance1
(
35
points)

5.5k
views
gate2007it
graphtheory
spanningtree
normal
+72
votes
8
answers
2
GATE201238
Let $G$ be a complete undirected graph on $6$ vertices. If vertices of $G$ are labeled, then the number of distinct cycles of length $4$ in $G$ is equal to $15$ $30$ $90$ $360$
answered
Jan 3
in
Graph Theory
by
JashanArora
Loyal
(
6.9k
points)

11.5k
views
gate2012
graphtheory
normal
markstoall
counting
+46
votes
4
answers
3
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
Jan 3
in
Graph Theory
by
JashanArora
Loyal
(
6.9k
points)

4.9k
views
gate2004
graphtheory
permutationandcombination
normal
counting
+1
vote
1
answer
4
NTA NET DEC2019( shortest distance)
Consider a weighted directed graph. The current shortest distance from sources S to node x is represented by d[v] = 29 . d[u] = 15 , w[u,v] = 12. What is the updated value of d[v]based on current information? 1) 29 2) 27 3) 25 4) 17
answered
Dec 26, 2019
in
Graph Theory
by
`JEET
Boss
(
19.2k
points)

79
views
+18
votes
4
answers
5
GATE2015154
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_______________.
answered
Dec 24, 2019
in
Graph Theory
by
scholaraniket
Junior
(
515
points)

5.7k
views
gate20151
graphtheory
graphconnectivity
normal
graphplanarity
outofsyllabusnow
numericalanswers
+2
votes
2
answers
6
Euler Path
Which of the following Graph has Euler Path but is not an Euler Graph? A. K1,1 B.K2,10 C.K2,11 D.K10,11.
answered
Dec 24, 2019
in
Graph Theory
by
Nirmal Gaur
Active
(
2.3k
points)

443
views
graphtheory
eulergraph
eulerpath
0
votes
1
answer
7
no of simple graph possible with 6 vertices and 4 edges is ?
answered
Dec 23, 2019
in
Graph Theory
by
mesh90
(
61
points)

334
views
+40
votes
11
answers
8
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
Dec 20, 2019
in
Graph Theory
by
shivam001
Junior
(
987
points)

5.1k
views
gate20143
graphtheory
graphconnectivity
normal
+31
votes
4
answers
9
GATE20021.25, ISRO200830, ISRO20166
The maximum number of edges in a nnode undirected graph without self loops is $n^2$ $\frac{n(n1)}{2}$ $n1$ $\frac{(n+1)(n)}{2}$
answered
Dec 20, 2019
in
Graph Theory
by
shivam001
Junior
(
987
points)

5.8k
views
gate2002
graphtheory
easy
isro2008
isro2016
graphconnectivity
+69
votes
8
answers
10
GATE2014151
Consider an undirected graph $G$ where selfloops are not allowed. The vertex set of $G$ is $\{(i,j) \mid1 \leq i \leq 12, 1 \leq j \leq 12\}$. There is an edge between $(a,b)$ and $(c,d)$ if $ac \leq 1$ and $bd \leq 1$. The number of edges in this graph is______.
answered
Dec 20, 2019
in
Graph Theory
by
shivam001
Junior
(
987
points)

8.6k
views
gate20141
graphtheory
numericalanswers
normal
graphconnectivity
+40
votes
7
answers
11
GATE200336
How many perfect matching are there in a complete graph of $6$ vertices? $15$ $24$ $30$ $60$
answered
Dec 19, 2019
in
Graph Theory
by
JashanArora
Loyal
(
6.9k
points)

5.5k
views
gate2003
graphtheory
graphmatching
normal
+7
votes
4
answers
12
ISRO201135
How many edges are there in a forest with $v$ vertices and $k$ components? $(v+1)  k$ $(v+1)/2  k$ $v  k$ $v + k$
answered
Dec 17, 2019
in
Graph Theory
by
Debjit0007
(
55
points)

2.4k
views
isro2011
graphtheory
+1
vote
2
answers
13
UGCNETJune2014II23
Consider a complete bipartite graph $k_{m,n}$. For which values of $m$ and $n$ does this, complete graph have a Hamilton circuit $m = 3, n = 2$ $m = 2, n = 3$ $m = n > 2$ $m = n > 3$
answered
Dec 12, 2019
in
Graph Theory
by
JashanArora
Loyal
(
6.9k
points)

1.5k
views
ugcnetjune2014ii
graphtheory
hamiltonian
+23
votes
3
answers
14
TIFR2018A9
How many ways are there to assign colours from range $\left\{1,2,\ldots,r\right\}$ to vertices of the following graph so that adjacent vertices receive distinct colours? $r^{4}$ $r^{4}  4r^{3}$ $r^{4}5r^{3}+8r^{2}4r$ $r^{4}4r^{3}+9r^{2}3r$ $r^{4}5r^{3}+10r^{2}15r$
answered
Dec 11, 2019
in
Graph Theory
by
neeraj_bhatt
(
335
points)

1k
views
tifr2018
graphtheory
graphcoloring
+9
votes
5
answers
15
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
Dec 6, 2019
in
Graph Theory
by
V0id
(
77
points)

4k
views
gate2019
engineeringmathematics
discretemathematics
graphtheory
graphconnectivity
+39
votes
9
answers
16
GATE19941.6, ISRO200829
The number of distinct simple graphs with up to three nodes is $15$ $10$ $7$ $9$
answered
Dec 3, 2019
in
Graph Theory
by
JashanArora
Loyal
(
6.9k
points)

10.5k
views
gate1994
graphtheory
permutationandcombination
normal
isro2008
counting
+8
votes
9
answers
17
GATE201912
Let $G$ be an undirected complete graph on $n$ vertices, where $n > 2$. Then, the number of different Hamiltonian cycles in $G$ is equal to $n!$ $(n1)!$ $1$ $\frac{(n1)!}{2}$
answered
Dec 1, 2019
in
Graph Theory
by
JashanArora
Loyal
(
6.9k
points)

4.1k
views
gate2019
engineeringmathematics
discretemathematics
graphtheory
graphconnectivity
0
votes
2
answers
18
self doubt
What is the general formula for number of simple graph having n unlabelled vertices ??
answered
Nov 30, 2019
in
Graph Theory
by
Muneendra1337
(
11
points)

80
views
simplegraph
+18
votes
9
answers
19
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
Nov 17, 2019
in
Graph Theory
by
Shailendra_
Junior
(
629
points)

6.4k
views
gate2018
graphtheory
graphsearch
normal
+1
vote
1
answer
20
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
Nov 15, 2019
in
Graph Theory
by
mohithjagalmohanan
(
43
points)

91
views
graphtheory
graphalgorithms
graphconnectivity
multistagegraph
directedacyclicgraph
dag
+2
votes
2
answers
21
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
Nov 12, 2019
in
Graph Theory
by
SPodder
(
13
points)

53
views
cmi2018
graphtheory
shortestpath
+1
vote
1
answer
22
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, 2019
in
Graph Theory
by
`JEET
Boss
(
19.2k
points)

64
views
cmi2016
graphtheory
graphconnectivity
+27
votes
4
answers
23
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, 2019
in
Graph Theory
by
shaktisingh
Junior
(
537
points)

2.8k
views
gate2006
graphtheory
normal
graphconnectivity
+2
votes
3
answers
24
Made easy
What is the chromatic number of following graphs? 1) 2)
answered
Oct 16, 2019
in
Graph Theory
by
chirudeepnamini
Active
(
4.5k
points)

198
views
graphcoloring
discrete
engineeringmathematics
+1
vote
1
answer
25
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, 2019
in
Graph Theory
by
Mac2
(
11
points)

134
views
discretemathematics
graphtheory
+33
votes
3
answers
26
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, 2019
in
Graph Theory
by
HeartBleed
Active
(
1k
points)

4.4k
views
gate2001
graphtheory
normal
counting
+1
vote
1
answer
27
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, 2019
in
Graph Theory
by
prashant jha 1
Loyal
(
5.9k
points)

43
views
cmi2018
graphtheory
graphconnectivity
descriptive
+3
votes
2
answers
28
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, 2019
in
Graph Theory
by
Raghava45
(
349
points)

302
views
ugcnetjune2019ii
graphtheory
0
votes
1
answer
29
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, 2019
in
Graph Theory
by
`JEET
Boss
(
19.2k
points)

40
views
cmi2019
graphconnectivity
0
votes
1
answer
30
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, 2019
in
Graph Theory
by
`JEET
Boss
(
19.2k
points)

32
views
cmi2018
graphtheory
graphconnectivity
graphmatching
independentset
descriptive
+14
votes
3
answers
31
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, 2019
in
Graph Theory
by
rohith1001
Active
(
2.1k
points)

992
views
isi2016
graphtheory
trees
descriptive
+1
vote
1
answer
32
CMI2019A7
An interschool basketball tournament is being held at the Olympic sports complex. There are multiple basketball courts. Matches are scheduled in parallel, with staggered timings, to ensure that spectators always have some match or other available to watch. Each match ... solve? Find a minimal colouring. Find a minimal spanning tree. Find a minimal cut. Find a minimal vertex cover.
answered
Sep 14, 2019
in
Graph Theory
by
`JEET
Boss
(
19.2k
points)

68
views
cmi2019
graphtheory
graphcoloring
spanningtree
vertexcover
descriptive
+1
vote
0
answers
33
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, 2019
in
Graph Theory
by
gatecse
Boss
(
17.5k
points)

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

181
views
graphtheory
graphcoloring
madeeasytestseries
madeeasytestseries2018
0
votes
1
answer
35
CUTSET
answered
Sep 1, 2019
in
Graph Theory
by
Devvrat Tyagi
(
159
points)

83
views
+28
votes
6
answers
36
GATE2014251
A cycle on $n$ vertices is isomorphic to its complement. The value of $n$ is _____.
answered
Aug 21, 2019
in
Graph Theory
by
King Suleiman
Active
(
1.2k
points)

4.3k
views
gate20142
graphtheory
numericalanswers
normal
graphisomorphism
nongate
+2
votes
2
answers
37
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, 2019
in
Graph Theory
by
IamDRD
(
109
points)

255
views
graphtheory
eulergraph
graphconnectivity
+1
vote
2
answers
38
#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, 2019
in
Graph Theory
by
Raghava45
(
349
points)

148
views
discretemathematics
graphtheory
+2
votes
3
answers
39
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, 2019
in
Graph Theory
by
tripu
(
11
points)

2k
views
ugcnetjune2015ii
discretemathematics
graphtheory
+3
votes
1
answer
40
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$
asked
Jul 2, 2019
in
Graph Theory
by
Arjun
Veteran
(
431k
points)

294
views
ugcnetjune2019ii
graphplanarity
handshakingtheorem
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
ISRO CSE 2020 PAPER ANALYSE
BARC OCES/DGFS 2020
ISI CMI PDF by GATE Overflow
Calculus Important Points
Management Trainee Recruitment COAL INDIA 2020
All categories
General Aptitude
1.9k
Engineering Mathematics
7.5k
Discrete Mathematics
5.2k
Mathematical Logic
2.1k
Set Theory & Algebra
1.4k
Combinatory
916
Graph Theory
824
Probability
1k
Linear Algebra
723
Calculus
592
Digital Logic
2.9k
Programming and DS
4.9k
Algorithms
4.4k
Theory of Computation
6.2k
Compiler Design
2.1k
Operating System
4.5k
Databases
4.1k
CO and Architecture
3.4k
Computer Networks
4.2k
Non GATE
1.4k
Others
1.4k
Admissions
595
Exam Queries
573
Tier 1 Placement Questions
23
Job Queries
72
Projects
18
Follow @csegate
Recent questions and answers in Graph Theory
Recent Blog Comments
Has anyone else challenged the questions on...
@nkg_master9  For getting selected for the...
Nowhere it's mentioned.
@bond  Is it mentioned that you have to score at...
I think cutoff won't cross 85
50,737
questions
57,385
answers
198,548
comments
105,361
users