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 tagged graphtheory
Webpage for Graph Theory:
+1
vote
1
answer
1
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.
asked
Sep 13, 2019
in
Graph Theory
by
gatecse
Boss
(
17.5k
points)

68
views
cmi2019
graphtheory
graphcoloring
spanningtree
vertexcover
descriptive
+2
votes
2
answers
2
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$
asked
Sep 13, 2019
in
Graph Theory
by
gatecse
Boss
(
17.5k
points)

53
views
cmi2018
graphtheory
shortestpath
0
votes
1
answer
3
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
asked
Sep 13, 2019
in
Graph Theory
by
gatecse
Boss
(
17.5k
points)

32
views
cmi2018
graphtheory
graphconnectivity
graphmatching
independentset
descriptive
+1
vote
1
answer
4
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.
asked
Sep 13, 2019
in
Graph Theory
by
gatecse
Boss
(
17.5k
points)

43
views
cmi2018
graphtheory
graphconnectivity
descriptive
+1
vote
0
answers
5
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
+3
votes
2
answers
6
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$
asked
Jul 2, 2019
in
Graph Theory
by
Arjun
Veteran
(
431k
points)

302
views
ugcnetjune2019ii
graphtheory
0
votes
1
answer
7
Doubt on Bipartite Graph
What is T.C. to find maximum number of edges to be added to a tree so that it stays as a bipartite graph? Now my question is, why do we need to add edges to make a tree bipartite? A tree is already bipartite graph. Right?? Again how do we add edges in it?? Is BFS or DFS do any improvement in such a tree?? How to think such a question??
asked
Jun 2, 2019
in
Algorithms
by
srestha
Veteran
(
119k
points)

87
views
graphtheory
algorithms
+2
votes
1
answer
8
ACE ACADEMY BOOKLET
Which of the following is $\textbf{not}$ TRUE? (a) In a complete graph $K_n$ ($n$ $\geq$ $3$), Hamiltonian cycle exists for all n. (b) In a complete bipartite graph $K_{m,n}$ (m $\geq$ 2 and n $\geq$2), Hamiltonian cycle exists $\Leftrightarrow$ ... Hamiltonian cycle exits for all $n$ (d) In a wheel graph $W_n$ ($n \geq 4$), Hamiltonian cycle exits $\Leftrightarrow$ $n$ is even.
asked
May 26, 2019
in
Graph Theory
by
`JEET
Boss
(
19.2k
points)

85
views
graphtheory
discretemathematics
+1
vote
2
answers
9
#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.
asked
May 26, 2019
in
Graph Theory
by
`JEET
Boss
(
19.2k
points)

148
views
discretemathematics
graphtheory
+1
vote
1
answer
10
Made easy Test Series:Graph Theory+Automata
Consider a graph $G$ with $2^{n}$ vertices where the level of each vertex is a $n$ bit binary string represented as $a_{0},a_{1},a_{2},.............,a_{n1}$, where each $a_{i}$ is $0$ or $1$ ... and $y$ denote the degree of a vertex $G$ and number of connected component of $G$ for $n=8.$ The value of $x+10y$ is_____________
asked
May 23, 2019
in
Graph Theory
by
srestha
Veteran
(
119k
points)

157
views
madeeasytestseries
graphtheory
theoryofcomputation
+5
votes
0
answers
11
IISc CSA  Research Interview Question
Prove that the rank of the Adjacency Matrix which is associated with a $k$ regular graph is $k.$
asked
May 22, 2019
in
Graph Theory
by
ankitgupta.1729
Boss
(
17.1k
points)

106
views
graphtheory
linearalgebra
+2
votes
2
answers
12
GateForum Question Bank :Graph Theory
What is the probability that there is an edge in an undirected random graph having 8 vertices? 1 1/8
asked
May 19, 2019
in
Graph Theory
by
Hirak
Active
(
3.6k
points)

161
views
graphtheory
discretemathematics
0
votes
2
answers
13
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.
asked
May 12, 2019
in
Graph Theory
by
chandan2teja
(
147
points)

107
views
graphtheory
0
votes
1
answer
14
IIIT PGEE 2019
Which of the following gives O(1) complexity if we want to check whether an edge exists between two given nodes in a graph? Adjacency List Adjacency Matrix Incidence Matrix None of these
asked
Apr 29, 2019
in
DS
by
manikgupta123
(
81
points)

153
views
iiithpgee
graphtheory
timecomplexity
+1
vote
1
answer
15
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?
asked
Apr 28, 2019
in
Graph Theory
by
gmrishikumar
Active
(
2.2k
points)

91
views
graphtheory
graphalgorithms
graphconnectivity
multistagegraph
directedacyclicgraph
dag
0
votes
0
answers
16
ISI2017PCBCS1(b)
Show that if the edge set of the graph $G(V,E)$ with $n$ nodes can be partitioned into $2$ trees, then there is at least one vertex of degree less than $4$ in $G$.
asked
Apr 8, 2019
in
Graph Theory
by
akash.dinkar12
Boss
(
42.5k
points)

62
views
isi2017pcbcs
engineeringmathematics
discretemathematics
graphtheory
graphconnectivity
descriptive
0
votes
0
answers
17
Graph Decomposition
What is Graph Decomposition & is it in the syllabus? If it is then please can anyone share some online resources for it. Thank you.
asked
Mar 17, 2019
in
Graph Theory
by
noxevolution
(
101
points)

38
views
graphtheory
0
votes
0
answers
18
Narsingh deo
What is meant by edge disjoint hamiltonian circuits in a graph
asked
Mar 5, 2019
in
Graph Theory
by
Winner
(
445
points)

80
views
graphtheory
+1
vote
0
answers
19
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
Feb 18, 2019
in
Graph Theory
by
Sayan Bose
Loyal
(
7.4k
points)

108
views
jest
graphtheory
+8
votes
9
answers
20
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, 2019
in
Graph Theory
by
Arjun
Veteran
(
431k
points)

4.1k
views
gate2019
engineeringmathematics
discretemathematics
graphtheory
graphconnectivity
+9
votes
5
answers
21
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, 2019
in
Graph Theory
by
Arjun
Veteran
(
431k
points)

4k
views
gate2019
engineeringmathematics
discretemathematics
graphtheory
graphconnectivity
+1
vote
0
answers
22
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, 2019
in
Graph Theory
by
Ashish Goyal
(
433
points)

143
views
graphmatching
discretemathematics
graphtheory
testseries
0
votes
2
answers
23
#GRAPH THEORY
A simple regular graph n vertices and 24 edges, find all possible values of n.
asked
Jan 29, 2019
in
Graph Theory
by
amit166
Junior
(
775
points)

114
views
graphtheory
0
votes
0
answers
24
Counting
asked
Jan 25, 2019
in
Graph Theory
by
screddy1313
(
481
points)

51
views
discretemathematics
graphtheory
engineeringmathematics
chromaticnumbers
#counting
0
votes
0
answers
25
Number of sub graphs possible
Number of labelled subgraphs possible for the graph given below______________
asked
Jan 25, 2019
in
DS
by
Nandkishor3939
Active
(
1.3k
points)

109
views
graphtheory
datastructures
0
votes
1
answer
26
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, 2019
in
Graph Theory
by
sudharshan
(
289
points)

87
views
discretemathematics
graphtheory
testseries
0
votes
0
answers
27
Homomorphic and Isomorphic graph
This a random question came into my mind… Are the below statements true: 1] If a graph is Homomorphic to our graph then it is also Isomorphic to that graph. 2]If a graph is Isomorphic to our graph then it is also Homomorphic graph.
asked
Jan 21, 2019
in
Set Theory & Algebra
by
Nandkishor3939
Active
(
1.3k
points)

61
views
graphisomorphism
graphtheory
grouptheory
0
votes
1
answer
28
MadeEasy Test Series: Discrete Mathematics  Graph Thoery
The number of labelled subgraphs possible for the graph given below.
asked
Jan 19, 2019
in
Graph Theory
by
snaily16
(
245
points)

344
views
madeeasytestseries
discretemathematics
graphtheory
0
votes
0
answers
29
Algorithm questions on graphs
let Gn be a complete graph on n vertices where n>2 such that each vertex is labeled by a distinct number 1,2, 3, 4, …, n , and each edge is labeled by the sum of its endpoint labels. Let f(Gn) be the minimum sum of edge labels in any path that touches every vertex in exactly once. How many values of satisfy f(Gn)2013 (mod n) ?___________
asked
Jan 19, 2019
in
Algorithms
by
Iamniks4
(
31
points)

34
views
graphtheory
0
votes
0
answers
30
Ace Test Series: Graph Theory  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, 2019
in
Graph Theory
by
Na462
Loyal
(
7k
points)

98
views
graphtheory
acetestseries
Page:
1
2
3
4
5
6
...
21
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
ISRO CSE 2020 PAPER ANALYSE
BARC OCES/DGFS 2020
ISI CMI PDF by GATE Overflow
Calculus Important Points
Management Trainee Recruitment COAL INDIA 2020
Follow @csegate
Recent questions tagged graphtheory
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,362
users