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

I forgot my password
All Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Lists
Previous
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 tagged graphtheory
Webpage for Graph Theory:
0
votes
0
answers
1
GATEBOOK2019DS21
The degree sequence of a simple graph is the sequence of the degrees of the nodes in the graph in decreasing order. Which of the following sequences can not be the degree sequence of any graph? 7, 5, 5, 3, 3, 2, 2, 2 6, 6, 6, 6, 3, 3, 2, 2, 1, 1 8, 7, 6, 4, 4, 3, 2, 2, 2 8, 7, 6, 6, 4, 4, 2, 2, 2 II and III III and IV IV only I and IV
asked
2 days
ago
in
Programming
by
GATEBOOK
(
471
points)

19
views
gb2019ds2
graphtheory
degreeofgraph
0
votes
1
answer
2
GATEBOOK2019DS23
A quinpartite graph is a graph whose vertices can be partitioned into five groups such that no two vertices in same group are connected via some edge. The maximum number of edges in a quinpartite graph with $10$ vertices, where cardinalities of those five sets are given as $\{2,3,2,1,2\},$ is: $16$ $20$ $26$ $39$
asked
2 days
ago
in
Programming
by
GATEBOOK
(
471
points)

23
views
gb2019ds2
graphtheory
graphconnectivity
0
votes
0
answers
3
virtual gate graph theory
i am getting 6 as answer
asked
3 days
ago
in
Graph Theory
by
Prince Sindhiya
Active
(
3.6k
points)

49
views
discretemathematics
graphtheory
0
votes
1
answer
4
Complete Matching
Consider the Bipartite graph shown. If four edges are chosen at random, what is the probability that they form a complete matching from V1 to V2 ? A. 0.039 B. 0.052 C. 0.071 D. 0.083
asked
5 days
ago
in
Mathematical Logic
by
Na462
Loyal
(
6.4k
points)

28
views
graphmatching
graphtheory
discretemathematics
+2
votes
2
answers
5
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? $A)$ Vertex $n$ has degree ... connected $C)$ There is a path from vertex $1$ to vertex $n$ $D)$ Spanning tree will include edge connecting vertex $1$ and vertex $n$
asked
Oct 10
in
Graph Theory
by
Lakshman Patel RJIT
Loyal
(
9.6k
points)

51
views
discretemathematics
graphtheory
0
votes
1
answer
6
Bipartite graph
The number of ways to properly color (using just sufficient colors) a connected graph without any cycle using five colors, such a way that no two adjacent nodes have the same color?
asked
Oct 10
in
Graph Theory
by
Lakshman Patel RJIT
Loyal
(
9.6k
points)

45
views
discretemathematics
graphtheory
0
votes
1
answer
7
Complete Graph
Consider the following graph: Number of the Hamiltonian cycles starting and ending point at $ A$ is _______
asked
Oct 10
in
Graph Theory
by
Lakshman Patel RJIT
Loyal
(
9.6k
points)

64
views
engineeringmathematics
discretemathematics
graphtheory
0
votes
0
answers
8
Mathematics
asked
Oct 4
in
Set Theory & Algebra
by
jatinkumar
(
223
points)

21
views
graphtheory
discretemathematics
0
votes
0
answers
9
Made easy,graphs
let G be an undirected graph. consider a depthfirst traversal of G, and let T be the resulting depthfirst search tree. let you be a vertex in G and let V be the first new (unvisited) vortex visited after visiting you in the traversal. which of the following statement is always true?
asked
Oct 1
in
DS
by
KrishY
(
7
points)

39
views
graphtheory
+1
vote
0
answers
10
UGCNET CS 2017
An undirected graph G (V, E) contains n (n > 2) nodes named v1 , v2 ,...,vn. Two nodes vi and vj are connected if and only if 0 < │ i − j│ ≤2. Each edge (vi , vj ) is assigned a weight i+j. The cost of the minimum spanning tree of such a graph with 10 nodes is: A) 88 B)91 C)49 D)21
asked
Sep 28
in
Graph Theory
by
aditi19
Junior
(
863
points)

25
views
ugcnetnov2017iii
graphtheory
0
votes
0
answers
11
Can Null Graph be a valid Matching
Definition of valid matching says that if every vertex is incident with atmost one vertex then it is a matching but I have seen coaching material note which includes null graph as a matching.I am confused please help.
asked
Sep 28
in
Graph Theory
by
sripo
(
293
points)

8
views
graphtheory
discretemathematics
0
votes
0
answers
12
General query of Graph Theory
$1)$ Is there any general formula for maximum degree (if possible also minimum degree) of a vertex in a graph G? $2)$ Is there any relationship between indegree and outdegree of a graph?
asked
Sep 25
in
Graph Theory
by
srestha
Veteran
(
98.4k
points)

30
views
graphtheory
discretemathematics
general
0
votes
1
answer
13
Graph Coloring
A vertex colouring with four colours of a graph G = (V, E) is a mapping V → {R, G, B, Y }. So that any two adjacent vertices does not same colour. Consider the below graphs: The number of vertex colouring possible with 4 colours are _________.
asked
Sep 21
in
Graph Theory
by
srestha
Veteran
(
98.4k
points)

63
views
graphtheory
graphcoloring
0
votes
0
answers
14
Bipartite Graph
Which of the following complete bipartite graphs will have Hamiltonian cycle? $a)K_{3,3}$ $b)K_{2,4}$
asked
Sep 21
in
Graph Theory
by
srestha
Veteran
(
98.4k
points)

53
views
graphtheory
engineeringmathematics
0
votes
1
answer
15
Graph Theory
Please help with the following: 1)How to determine if a graph is bipartite or not? 2)What is meant by ordered pair in case of a directed graph and unordered pair in case of an undirected graph?
asked
Sep 18
in
Graph Theory
by
Devshree Dubey
Boss
(
13.6k
points)

21
views
graphtheory
0
votes
2
answers
16
ME test series.
How 14? I am not able to understand. Why not 30.
asked
Sep 6
in
Graph Theory
by
aoao
(
77
points)

73
views
graphtheory
0
votes
0
answers
17
Doubt
What is converse of a graph?
asked
Sep 1
in
Graph Theory
by
aditi19
Junior
(
863
points)

15
views
graphtheory
0
votes
1
answer
18
GATE Minimum Spanning Trees
Q1) Why is the path between a pair of vertices in a minimum Spanning tree of an undirected graph not the shortest( minimum weight) path?
asked
Aug 31
in
Mathematical Logic
by
Nidhi Budhraja
(
121
points)

38
views
minimumspanningtrees
spanningtree
graphtheory
graphalgorithms
algorithms
+2
votes
1
answer
19
Graph theory
Stmt 1: A simple graph is necessarily connected if E > (n1)*(n2)/2. Stmt2: A simple graph with n vertices and k components has at least nk edges. Can you please explain how are these results derived?
asked
Aug 26
in
Mathematical Logic
by
Nidhi Budhraja
(
121
points)

65
views
graphtheory
discretemathematics
graphconnectivity
+1
vote
0
answers
20
Kenneth Rosen Discrete Mathematics
DIRAC’S THEOREM: If G is a simple graph with n vertices with n ≥ 3 such that the degree of every vertex in G is at least n/2, then G has a Hamilton circuit. The below graph does not follow the above rule but still have a Hamilton circuit.
asked
Aug 25
in
Graph Theory
by
CJ147
(
73
points)

28
views
graphtheory
hamiltoncircuit
diractheorem
+1
vote
1
answer
21
Number of Eulerian Graphs
Find the number of connected Eulerian graphs with 6 unlabelled vertices. Draw each of them. Note: I'm looking for a fast procedure don't comment just the numerical answer.
asked
Aug 24
in
Graph Theory
by
Mk Utkarsh
Boss
(
20.1k
points)

55
views
graphtheory
0
votes
0
answers
22
Cosets subgraphs legranges thm
I am not able to understand clearly the concepts related to cosets, subgroups, lattice theory.Can someone suggest references to clarify my understanding of each topic?
asked
Aug 22
in
Mathematical Logic
by
Nidhi Budhraja
(
121
points)

11
views
graphtheory
cosets
0
votes
1
answer
23
Made Easy algorithms
How many edge disjoint spanning trees are possible for a undirected complete connected graph of n vertices?
asked
Aug 13
in
Algorithms
by
Sambhrant Maurya
Junior
(
755
points)

57
views
algorithms
spanningtree
graphtheory
+1
vote
2
answers
24
Graph theory Modified
What is the maximum integer value m such that every simple connected graph with r vertices and r+2 edges contains at least m different spanning trees ? 1)1 2)4 3)8 4)m
asked
Aug 13
in
Graph Theory
by
srestha
Veteran
(
98.4k
points)

144
views
graphtheory
discretemathematics
0
votes
1
answer
25
Test Datasructures
Statement I : If a directed graph G is cyclic but can be made acyclic by removing 1 edge then a DFS will encounter exactly 1 Backedge Statement II : A graph G has a cycle if DFS finds at least 1 Backedge Which of the following option is correct ? ... option is correct(Statement 1 is false and Statement 2 is true but answer given is 1, please tell me where i am making mistake.
asked
Aug 11
in
Algorithms
by
Prince Sindhiya
Active
(
3.6k
points)

17
views
graphtheory
0
votes
0
answers
26
Show that T is a maximum spanning tree for G
asked
Jul 24
in
Graph Theory
by
abram19000
(
7
points)

31
views
graphtheory
graphalgorithms
0
votes
1
answer
27
ACE Bits and bYtes
Minimum no of edges necessary in a simple graph with 10 vertices to ensure connectivity is_______.
asked
Jul 24
in
Graph Theory
by
abhishek1995_cse
(
131
points)

97
views
graphtheory
graphconnectivity
+1
vote
1
answer
28
ACE Bits And Bytes
Number of perfect matching in Wn (n>=4 and n is even) _________.
asked
Jul 24
in
Graph Theory
by
abhishek1995_cse
(
131
points)

51
views
graphtheory
graphmatching
gate2019
0
votes
1
answer
29
me test
A simple graph with n vertices is constructed by randomly and independently placing an edge between every two vertices with probability p. What is the expected no. of nodes with degree 2?
asked
Jul 17
in
Graph Theory
by
ronin_codex
(
7
points)

56
views
probability
graphtheory
expectation
simplegraph
0
votes
0
answers
30
graph theory
10.A graph G has any two vertices connected by exactly one path. Find the Number of ways we can properly colour G it we are provided with 10 colours.
asked
Jul 14
in
Graph Theory
by
poojasharma123
(
89
points)

77
views
graphtheory
Page:
1
2
3
4
5
6
...
18
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
List of Available Exams
New Assignment on Network programming : P2P simulation
Theory of Computation  GO Classroom
Probability  GO Classroom
Daily Quiz
Follow @csegate
Gatecse
Recent questions tagged graphtheory
Recent Blog Comments
Nice 2 know. You are welcome. :)
Hello @Arjun, I got books now...thanks for your...
You may contact FedEx local delivery office. It...
Yes you are right, it's showing this status from...
FedEx delivery is shown and as per that it is out...
40,903
questions
47,558
answers
146,288
comments
62,305
users