The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
GATE Overflow
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
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions. For hardcopy of previous year questions please see
here
Recent questions in Graph Theory
Recent
Hot!
Most votes
Most answers
Most views
Featured
Previous GATE
Web Page
Connectivity,
Matching,
Coloring.
Recent
Hot!
Most votes
Most answers
Most views
Featured
Previous GATE
0
votes
0
answers
1
JEST 2019
A directed graph with n vertices, in which each vertex has exactly 3 outgoing edges. Which one is true? A) All the vertices have indegree = 3 . B) Some vertices will have indegree exactly 3. C)Some vertices have indegree atleast 3. D) Some of the vertices have indegree atmost 3
asked
2 days
ago
in
Graph Theory
by
Sayan Bose
Loyal
(
5.9k
points)

29
views
jest
graphtheory
0
votes
0
answers
2
JEST 2019 Descriptive Q2 (8 Marks)
Given a sequence $a_1$, $a_2$ , $a_3$ ... $a_n$ of any different positive integers, exhibit an arrangement of integers between 1 and $n^2$ which has no increasing or decreasing subsequence of length n+1.
asked
2 days
ago
in
Graph Theory
by
dan31
Junior
(
657
points)

24
views
jest
2019
discretemathematics
0
votes
0
answers
3
JEST 2019 Descriptive Q1 (8 Marks)
Suppose that G contains a cycle C, and a path of length at least k between some two vertices of C. Show that G contains a cycle of length at least √k.
asked
2 days
ago
in
Graph Theory
by
dan31
Junior
(
657
points)

24
views
jest
2019
discretemathematics
0
votes
4
answers
4
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}$
asked
Feb 7
in
Graph Theory
by
Arjun
Veteran
(
384k
points)

1.9k
views
gate2019
engineeringmathematics
discretemathematics
graphtheory
graphconnectivity
+1
vote
1
answer
5
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
asked
Feb 7
in
Graph Theory
by
Arjun
Veteran
(
384k
points)

1.9k
views
gate2019
engineeringmathematics
discretemathematics
graphtheory
graphconnectivity
0
votes
1
answer
6
GATE 2019 8
Q.8 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 1. (n1)!/2 2. 1 3.(n1)! 4. n!
asked
Feb 7
in
Graph Theory
by
Ram Swaroop
Active
(
2.2k
points)

202
views
usergate2019
usermod
discretemathematics
graphtheory
0
votes
2
answers
7
GATE2019
What is the total number of different Hamiltonian cycles for the complete graph of n vertices?
asked
Feb 3
in
Graph Theory
by
Atul Sharma 1
(
129
points)

692
views
0
votes
0
answers
8
Abelian group
A quick question Is every multiplication modulo function a Abelian group....Or is it the case that the function should have prime number as modulo
asked
Feb 2
in
Graph Theory
by
Nandkishor3939
Active
(
1.2k
points)

32
views
0
votes
0
answers
9
GeeksforGeeks
Let G be a graph with no isolated vertices, and let M be a maximum matching of G. For each vertex v not saturated by M, choose an edge incident to v. Let T be the set of all the chosen edges, and let L = M ∪ T. Which of the following option is TRUE? A L is always ... G. B L is always a minimum edge cover of G. C Both (A) and (B) D Neither (A) nor (B) Can anyone pls help solving this?
asked
Jan 30
in
Graph Theory
by
Ashish Goyal
(
337
points)

90
views
graphmatching
discretemathematics
graphtheory
testseries
0
votes
0
answers
10
Madeeasy
A graph G is called self complementary iff G is isomorphic to its complement. Let X be a self complementary graph. Which of the following is a viable possibility with regards to the connectivity of X and X', where X' denotes the complement of X, ... answer such questions. So the conclusion is "Every sell complementary graph is cormected". So option (d) is the correct answer.
asked
Jan 29
in
Graph Theory
by
mehul vaidya
Active
(
3k
points)

24
views
0
votes
0
answers
11
selfdoubtMEtestseries
we define a new measure ,called GoldIndex(G,C).it takes two arguments as input namely a graph G and set of colors C respectively . the subroutine outputs an integer denoting the number of ways assigning colors to vertices in G such that at least two vertices ... 't know where m i going wrong ,please help me i know their solution is correct but i want to verify my approach
[closed]
asked
Jan 29
in
Graph Theory
by
Prateek Raghuvanshi
Loyal
(
9.6k
points)

64
views
0
votes
1
answer
12
#GRAPH THEORY
A simple regular graph n vertices and 24 edges, find all possible values of n.
asked
Jan 29
in
Graph Theory
by
amit166
Junior
(
693
points)

59
views
graphtheory
0
votes
0
answers
13
max weighted MST possible
Let G be a complete undirected graph on 5 vertices 10 edges, with weights being 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. Let X be the value of the maximum possible weight a MST of G can have. Then the value of x will be_____ the answer to this question is given as 11 but there is no procedure given . Please ,can anyone help me out in understanding the procedure
asked
Jan 26
in
Graph Theory
by
Nandkishor3939
Active
(
1.2k
points)

64
views
mst
0
votes
0
answers
14
Made Easy Practice Book
The number of labelled subgraph possible for the graph given below are ________.
asked
Jan 25
in
Graph Theory
by
Shankar Kakde
(
369
points)

29
views
0
votes
0
answers
15
Counting
asked
Jan 25
in
Graph Theory
by
screddy1313
(
401
points)

29
views
discretemathematics
graphtheory
engineeringmathematics
chromaticnumbers
#counting
0
votes
0
answers
16
SelfDoubt
A graph with each vertex has even degree contain Hamiltonian Cycle. True/False plz explain how to ensure Hamiltonian Cycle.
asked
Jan 25
in
Graph Theory
by
Abhisek Tiwari 4
Active
(
3.9k
points)

44
views
0
votes
1
answer
17
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?
asked
Jan 24
in
Graph Theory
by
sudharshan
(
289
points)

59
views
discretemathematics
graphtheory
testseries
0
votes
1
answer
18
ACE TEST SERIES QUESTION ON Graph Theory
asked
Jan 24
in
Graph Theory
by
Shankar Kakde
(
369
points)

33
views
0
votes
0
answers
19
SelfDoubt
Checking for Euler Path i.A graph has Euler path if exactly two vertices is of odd degree. if a graph have euler circuit=>all vertices even degree=>euler circuit which already cover euler path. am i correct? i is necessary and sufficient condition? So for ... check either 1.Euler Circuit or 2.Exactly two odd degree then it will have euler path but not euler circuit. is it correct?
[closed]
asked
Jan 20
in
Graph Theory
by
Abhisek Tiwari 4
Active
(
3.9k
points)

30
views
0
votes
1
answer
20
Gateforum mock 2
asked
Jan 20
in
Graph Theory
by
Prince Sindhiya
Loyal
(
6.2k
points)

31
views
gateforumtestseries
+1
vote
1
answer
21
GATEBOOK2019 Mock Test139
Consider the collection of all un directed graphs with $10$ nodes and $6$ edges. Let M and m, respectively, be the maximum and minimum number of connected components in any graph in the collection. If a graph has no self loops and there is at most one edge between any pair of nodes, which of the ... $M = 10, \: m = 1$ $M = 7, \: m = 4$ $M = 6, \: m = 4$
asked
Jan 19
in
Graph Theory
by
GATEBOOK
Boss
(
15.3k
points)

127
views
gb2019mock1
+1
vote
2
answers
22
GATEBOOK2019 Mock Test140
The number of graphs possible with $5$ vertices and $3$ edges is ____ $10$ $15$ $5$ $120$
asked
Jan 19
in
Graph Theory
by
GATEBOOK
Boss
(
15.3k
points)

247
views
gb2019mock1
0
votes
0
answers
23
Number of Cut edges
If G is a connected simple graph with 10 vertices in which degree of every vertex is 2 then number of cut edges in G is ?
asked
Jan 19
in
Graph Theory
by
Na462
Loyal
(
8.6k
points)

44
views
algorithms
graphtheory
acetestseries
0
votes
0
answers
24
made easy adv mock
A graph G is self complementary iff G is isomorphoc to its complement.Let X be a self complementary graph.Which of the following is a viable possibility with regards to connectivity of X and X' ,where X' denotes the complement of X? a)both X and X' are ... X' is disconnected c)X' is connected and X' is disconnected d)both X and X' are connected ans is (d) pls explain
asked
Jan 18
in
Graph Theory
by
Gate Fever
Active
(
4.7k
points)

33
views
0
votes
1
answer
25
ME test series question on graph theory
asked
Jan 17
in
Graph Theory
by
Shankar Kakde
(
369
points)

55
views
graphtheory
0
votes
2
answers
26
Applied Course 2019 Mock136
Naveen invited seven of his friends to a party. At the party, several pairs of people shook hands, although no one shook hands with themselves or shook hands with the same person more than once. After the party, Naveen asked each of his seven friends ... distinct positive integers. Given that his friends were truthful, how many hands did Naveen shake? $4$ $5$ $6$ $7$
asked
Jan 16
in
Graph Theory
by
Applied Course
Junior
(
757
points)

81
views
appldcourse2019mock1
graphtheory
0
votes
1
answer
27
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?
asked
Jan 16
in
Graph Theory
by
himgta
Active
(
3.6k
points)

75
views
+1
vote
2
answers
28
Tripartite Graph
The number of vertices,edges and colors required for proper coloring in Tripartite graph K<3,2,5> will be : 10 , 31 , 3 10 , 30 , 3 10 , 30 , 2 None
asked
Jan 16
in
Graph Theory
by
Na462
Loyal
(
8.6k
points)

58
views
graphtheory
discretemathematics
madeeasytestseries
+1
vote
1
answer
29
Vertex Connectivity
The Vertex Connectivity of Graph is : 1 2 3 None
asked
Jan 16
in
Graph Theory
by
Na462
Loyal
(
8.6k
points)

48
views
graphtheory
graphconnectivity
madeeasytestseries
0
votes
0
answers
30
Ace Academy Test series
If a 2 regular graph G has a perfect matching, then which of the following is NOT true? 1. G is a cycle graph 2. Chromatic number of G is 2 3. Every component of G is even cycle 4. G is a bipartite graph
asked
Jan 16
in
Graph Theory
by
Chaitrasj
Junior
(
893
points)

44
views
Page:
1
2
3
4
5
6
...
27
next »
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 keys are out now.
JEST 2019 MEMORY BASED QUESTION PAPER
Relax... But....
Barc : Arjun Sir
JEST Sample Question
All categories
General Aptitude
1.5k
Engineering Mathematics
7.1k
Discrete Mathematics
4.9k
Mathematical Logic
1.9k
Set Theory & Algebra
1.3k
Combinatory
873
Graph Theory
802
Probability
1k
Linear Algebra
691
Calculus
491
Digital Logic
2.7k
Programming & DS
4.9k
Algorithms
4.2k
Theory of Computation
5.3k
Compiler Design
2.1k
Operating System
4k
Databases
4k
CO & Architecture
3.5k
Computer Networks
4k
Non GATE
1.4k
Others
1.5k
Admissions
556
Exam Queries
553
Tier 1 Placement Questions
23
Job Queries
69
Projects
18
Follow @csegate
Recent questions in Graph Theory
Recent Blog Comments
Only one question that is "no.of NOR gates"...
Hey, I'm new here, but can you explain to me why...
How to challenge the key???
There was this graph coloring chromatic number...
47,904
questions
52,285
answers
182,216
comments
67,720
users