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
0
votes
2
answers
1
UGCNETDec2006II: 3
The number of edges in a complete graph with N vertices is equal to: $N (N−1)$ $2N−1$ $N−1$ $N(N−1)/2$
answered
19 hours
ago
in
Graph Theory
by
immanujs
Active
(
3.8k
points)

18
views
ugcnetdec2006ii
0
votes
1
answer
2
NIELIT 2016 DEC Scientist B (CS)  Section B: 5
Let G be a simple undirected planar graph on $10$ vertices with $15$ edges. If G is a connected graph, then the number of bounded faces in any embedding of G on the plane is equal to: $3$ $4$ $5$ $6$
answered
1 day
ago
in
Graph Theory
by
smsubham
Boss
(
16.5k
points)

10
views
nielit2016decscientistbcs
0
votes
0
answers
3
NIELIT 2016 MAR Scientist B  Section B: 3
Maximum degree of any node in a simple graph with $n$ vertices is $n1$ $n$ $n/2$ $n2$
asked
2 days
ago
in
Graph Theory
by
Lakshman Patel RJIT
Veteran
(
61.3k
points)

9
views
nielit2016marscientistb
0
votes
1
answer
4
UGCNETDec2007II: 2
The number of edges in a complete graph with ‘n’ vertices is equal to : $n(n1)$ $\large\frac{n(n1)}{2}$ $n^2$ $2n1$
answered
4 days
ago
in
Graph Theory
by
chirudeepnamini
Loyal
(
5.3k
points)

21
views
ugcnetdec2007ii
0
votes
1
answer
5
UGCNETDec2004II: 4
The following lists are the degrees of all the vertices of a graph : $1,2,3,4,5$ $3,4,5,6,7$ $1, 4, 5, 8, 6$ $3,4,5,6$ (i) and (ii) (iii) and (iv) (iii) and (ii) (ii) and (iv)
answered
6 days
ago
in
Graph Theory
by
Divya Devi
(
23
points)

17
views
ugcnetdec2004ii
0
votes
0
answers
6
UGCNETDec2004II: 23
Weighted graph : Is a bidirectional graph. Is directed graph. Is graph in which number associated with arc. Eliminates table method.
asked
Mar 26
in
Graph Theory
by
jothee
Veteran
(
107k
points)

5
views
ugcnetdec2004ii
0
votes
2
answers
7
NIELIT July 2017_75
Choose the most appropriate definition of plane graph A) A simple graph which is isomorphic to Hamiltonian graph B) A graph drawn in a plane such away that if the vertex set of graph can be partitioned into two non  empty disjoint subset X and Y in such a way ... A graph drawn in a plane in such a way that any pair of edges meet only at their end vertices D) None of the option
answered
Mar 19
in
Graph Theory
by
topper98
Junior
(
589
points)

340
views
+3
votes
5
answers
8
NIELIT July 2017_73
For the graph shown, which of the following paths is a Hamilton circuit ? A) ABCDCFDEFAEA B) AEDCBAF C) AEFDCBA D) AFCDEBA
answered
Mar 19
in
Graph Theory
by
topper98
Junior
(
589
points)

628
views
0
votes
2
answers
9
NIELIT July 2017_72
The following graph has no Euler circuit because A) It has 7 vertices B) It is evenvalent (all vertices have even valence) C) It is not connected D) It does not have an Euler circuit
answered
Mar 19
in
Graph Theory
by
topper98
Junior
(
589
points)

361
views
0
votes
2
answers
10
NIELIT July 2017_71
Consider the following graph L and find the bridges, if any A) No bridge B) {d, e} C) {c, d} D) {c, d} and {c, f}
answered
Mar 19
in
Graph Theory
by
topper98
Junior
(
589
points)

395
views
+13
votes
6
answers
11
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
Mar 17
in
Graph Theory
by
immanujs
Active
(
3.8k
points)

4.7k
views
gate2019
engineeringmathematics
discretemathematics
graphtheory
graphconnectivity
0
votes
3
answers
12
NIELIT ScientistB Dec 2017_56
Let G be a simple undirected graph on $n=3x$ vertices ($x>=1$) with chromatic number 3, then maximum number of edges in G is : (A) $n(n1)/2$ (B) $n^{n2}$ (C) $nx$ (D) $n$
answered
Mar 8
in
Graph Theory
by
vivekgatecs2020
(
137
points)

460
views
+28
votes
3
answers
13
GATE20021.4
The minimum number of colours required to colour the vertices of a cycle with $n$ nodes in such a way that no two adjacent nodes have the same colour is $2$ $3$ $4$ $n2 \left \lfloor \frac{n}{2} \right \rfloor+2$
answered
Mar 7
in
Graph Theory
by
vivekgatecs2020
(
137
points)

3.1k
views
gate2002
graphtheory
graphcoloring
normal
+33
votes
4
answers
14
GATE20093
Which one of the following is TRUE for any simple connected undirected graph with more than $2$ vertices? No two vertices have the same degree. At least two vertices have the same degree. At least three vertices have the same degree. All vertices have the same degree.
answered
Mar 7
in
Graph Theory
by
vivekgatecs2020
(
137
points)

2.7k
views
gate2009
graphtheory
normal
degreeofgraph
+2
votes
2
answers
15
Zeal Test Series 2019: Graph Theory  Graph Coloring
what is index ?
answered
Mar 2
in
Graph Theory
by
Parth Narodia
(
23
points)

167
views
zeal
graphtheory
graphcoloring
zeal2019
+2
votes
3
answers
16
GATE2020CS52
Graph $G$ is obtained by adding vertex $s$ to $K_{3,4}$ and making $s$ adjacent to every vertex of $K_{3,4}$. The minimum number of colours required to edgecolour $G$ is _______
answered
Feb 27
in
Graph Theory
by
immanujs
Active
(
3.8k
points)

1.2k
views
gate2020cs
numericalanswers
grab
graphtheory
+10
votes
3
answers
17
GATE200510
Let $G$ be a simple connected planar graph with $13$ vertices and $19$ edges. Then, the number of faces in the planar embedding of the graph is: $6$ $8$ $9$ $13$
answered
Feb 21
in
Graph Theory
by
Pratyush Priyam Kuan
Active
(
1.1k
points)

1.4k
views
gate2005
graphtheory
graphplanarity
+31
votes
5
answers
18
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
Feb 20
in
Graph Theory
by
Pratyush Priyam Kuan
Active
(
1.1k
points)

6k
views
gate2002
graphtheory
easy
isro2008
isro2016
graphconnectivity
+24
votes
7
answers
19
GATE2006IT11
If all the edge weights of an undirected graph are positive, then any subset of edges that connects all the vertices and has minimum total weight is a Hamiltonian cycle grid hypercube tree
answered
Feb 20
in
Graph Theory
by
Pratyush Priyam Kuan
Active
(
1.1k
points)

2.1k
views
gate2006it
graphtheory
graphconnectivity
normal
+29
votes
5
answers
20
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
Feb 20
in
Graph Theory
by
Pratyush Priyam Kuan
Active
(
1.1k
points)

3k
views
gate2006
graphtheory
normal
graphconnectivity
+24
votes
2
answers
21
GATE200511
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$
answered
Feb 20
in
Graph Theory
by
Pratyush Priyam Kuan
Active
(
1.1k
points)

3k
views
gate2005
graphtheory
normal
graphconnectivity
+18
votes
5
answers
22
GATE2004IT5
What is the maximum number of edges in an acyclic undirected graph with $n$ vertices? $n1$ $n$ $n+1$ $2n1$
answered
Feb 20
in
Graph Theory
by
Pratyush Priyam Kuan
Active
(
1.1k
points)

2.1k
views
gate2004it
graphtheory
graphconnectivity
normal
+12
votes
3
answers
23
GATE19942.5
The number of edges in a regular graph of degree $d$ and $n$ vertices is ____________
answered
Feb 20
in
Graph Theory
by
Pratyush Priyam Kuan
Active
(
1.1k
points)

5.3k
views
gate1994
graphtheory
easy
graphconnectivity
descriptive
+23
votes
4
answers
24
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
Feb 20
in
Graph Theory
by
Pratyush Priyam Kuan
Active
(
1.1k
points)

1.1k
views
tifr2018
graphtheory
graphcoloring
+31
votes
4
answers
25
TIFR2017B1
A vertex colouring with three colours of a graph $G=(V, E)$ is a mapping $c: V \rightarrow \{R, G, B\}$ so that adjacent vertices receive distinct colours. Consider the following undirected graph. How many vertex colouring with three colours does this graph have? $3^9$ $6^3$ $3 \times 2^8$ $27$ $24$
answered
Feb 20
in
Graph Theory
by
Pratyush Priyam Kuan
Active
(
1.1k
points)

1.1k
views
tifr2017
graphtheory
graphcoloring
+25
votes
3
answers
26
GATE2008IT3
What is the chromatic number of the following graph? $2$ $3$ $4$ $5$
answered
Feb 20
in
Graph Theory
by
Pratyush Priyam Kuan
Active
(
1.1k
points)

2.3k
views
gate2008it
graphtheory
graphcoloring
normal
+25
votes
6
answers
27
GATE200477
The minimum number of colours required to colour the following graph, such that no two adjacent vertices are assigned the same color, is $2$ $3$ $4$ $5$
answered
Feb 19
in
Graph Theory
by
Pratyush Priyam Kuan
Active
(
1.1k
points)

2.9k
views
gate2004
graphtheory
graphcoloring
easy
0
votes
3
answers
28
TIFR2020B11
Which of the following graphs are bipartite? Only $(1)$ Only $(2)$ Only $(2)$ and $(3)$ None of $(1),(2),(3)$ All of $(1),(2),(3)$
answered
Feb 11
in
Graph Theory
by
nitin_kumar
(
273
points)

91
views
tifr2020
engineeringmathematics
graphtheory
graphcoloring
+43
votes
8
answers
29
GATE200336
How many perfect matching are there in a complete graph of $6$ vertices? $15$ $24$ $30$ $60$
answered
Feb 1
in
Graph Theory
by
rohit9
(
143
points)

5.9k
views
gate2003
graphtheory
graphmatching
normal
0
votes
1
answer
30
Virtual Gate Test Series: Discrete Mathematics  Graph Theory
Let $G$ be a graph on $n$ vertices with $4n16$ edges.Consider the following: 1. There is a vertex of degree smaller than $8$ in $G.$ 2. There is a vertex such that there are less than $16$ vertices at a distance exactly $2$ from it. Which of the following is TRUE: 1 only 2 only Both 1 and 2 Neither 1 nor 2
answered
Jan 29
in
Graph Theory
by
Pankajmjx
(
33
points)

168
views
discretemathematics
graphtheory
virtualgatetestseries
+51
votes
5
answers
31
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
(
45
points)

5.7k
views
gate2007it
graphtheory
spanningtree
normal
+75
votes
8
answers
32
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
(
8.3k
points)

12.2k
views
gate2012
graphtheory
normal
markstoall
counting
+48
votes
4
answers
33
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
(
8.3k
points)

5.1k
views
gate2004
graphtheory
permutationandcombination
normal
counting
+1
vote
1
answer
34
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.7k
points)

166
views
+18
votes
4
answers
35
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
(
547
points)

6k
views
gate20151
graphtheory
graphconnectivity
normal
graphplanarity
outofsyllabusnow
numericalanswers
+3
votes
2
answers
36
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)

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

384
views
+42
votes
11
answers
38
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
Active
(
1.2k
points)

5.4k
views
gate20143
graphtheory
graphconnectivity
normal
+71
votes
8
answers
39
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
Active
(
1.2k
points)

9.1k
views
gate20141
graphtheory
numericalanswers
normal
graphconnectivity
+7
votes
4
answers
40
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
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
BARC Interview Experience 2019
IITGN PGDIIT Fees/Placement/other info.
Online Python Programming Course by IIT Kanpur
CCMT (Portal for NIT admission) is now open
Generating Functions  All you need to know for GATE
All categories
General Aptitude
1.9k
Engineering Mathematics
7.6k
Discrete Mathematics
5.2k
Mathematical Logic
2.1k
Set Theory & Algebra
1.4k
Combinatory
919
Graph Theory
832
Probability
1k
Linear Algebra
735
Calculus
601
Digital Logic
2.9k
Programming and DS
5k
Algorithms
4.4k
Theory of Computation
6.2k
Compiler Design
2.2k
Operating System
4.5k
Databases
4.2k
CO and Architecture
3.4k
Computer Networks
4.2k
Non GATE
1.5k
Others
2.1k
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
Or IIT Kanpur?
how was it this year?
How you prepared and the resources from you...
please suggest me how to prepare for the barc...
They don't like textbook definition at all,if you...
51,925
questions
58,730
answers
200,106
comments
111,799
users