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
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
+2
votes
2
answers
1
ACE ACADEMY BOOKLET QUESTION
Let $G$ $=$ $(V, E)$ be a simple nonempty connected undirected graph, in which every vertex has degree 4. For any partition $V$ into two nonempty and nonoverlapping subsets $S$ and $T$. Which of the following is true? There are at least two edges that ... $S$ and one end point in $T$ There are exactly one edge that have one end point in $S$ and one end point in $T$
asked
May 26
in
Graph Theory
by
`JEET
Active
(
3.3k
points)

66
views
+1
vote
3
answers
2
Ace academy booklet #graph theory
Which of the following is $\textbf{not}$ TRUE? (a) In a complete graph $K_n$ ($n$ $\geq$ $3$), Euler circuit exists $\Leftrightarrow$ $n$ is odd. (b) In a complete bipartite graph $K_{m,n}$ (m $\geq$ 2 and n $\geq$2), Euler circuit exists ... Euler circuit exits for all $n$ (d) In a wheel graph $W_n$ ($n \geq 4$), Euler circuit exits $\Leftrightarrow$ $n$ is even.
asked
May 26
in
Graph Theory
by
`JEET
Active
(
3.3k
points)

34
views
+1
vote
1
answer
3
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
in
Graph Theory
by
`JEET
Active
(
3.3k
points)

23
views
graphtheory
discretemathematics
+1
vote
1
answer
4
#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
in
Graph Theory
by
`JEET
Active
(
3.3k
points)

21
views
discretemathematics
graphtheory
+1
vote
1
answer
5
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
in
Graph Theory
by
srestha
Veteran
(
111k
points)

67
views
madeeasytestseries
graphtheory
theoryofcomputation
+2
votes
0
answers
6
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
in
Graph Theory
by
ankitgupta.1729
Boss
(
13.2k
points)

68
views
graphtheory
linearalgebra
+2
votes
2
answers
7
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
in
Graph Theory
by
Hirak
Active
(
3k
points)

100
views
graphtheory
discretemathematics
0
votes
2
answers
8
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
in
Graph Theory
by
chandan2teja
(
75
points)

59
views
graphtheory
0
votes
0
answers
9
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
in
Graph Theory
by
gmrishikumar
Active
(
1.8k
points)

47
views
graphtheory
graphalgorithms
graphconnectivity
multistagegraph
directedacyclicgraph
dag
0
votes
0
answers
10
ISI2017PCBB1(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
in
Graph Theory
by
akash.dinkar12
Boss
(
40.4k
points)

38
views
isi2017pcbb
engineeringmathematics
discretemathematics
graphtheory
descriptive
0
votes
1
answer
11
selfdoubt
A graph with alternating edges and vertices is called a walk (we can repeat the number of vertices and edges any number of times) . A walk in which no edges are repeated is called a trial. A trial in which no vertices are repeated is called a path. A trial in which only the starting and ending vertices are repeated is called a circuit. Are the definitions correct??
asked
Mar 31
in
Graph Theory
by
Doraemon
(
179
points)

19
views
graph
0
votes
1
answer
12
self doubt
What is the general formula for number of simple graph having n unlabelled vertices ??
asked
Mar 31
in
Graph Theory
by
Doraemon
(
179
points)

47
views
simplegraph
0
votes
1
answer
13
Allen Career Institute: Spanning tree
Let $G$ be a simple undirected complete and weighted graph with vertex set $V = {0, 1, 2, . 99.}$ Weight of the edge $(u, v)$ is $\left  uv \right $ where $0\leq u, v\leq 99$ and $u\neq v$. Weight ... tree is______________ Doubt:Here asking for maximum weight spanning tree. So, there weight will be $0$ to every node. Isnot it? but answer given 7351.
asked
Mar 29
in
Graph Theory
by
srestha
Veteran
(
111k
points)

71
views
discretemathematics
+1
vote
1
answer
14
Allen Career Institute:Graph Theory
If G be connected planar graph with 12 vertices of deg 4 each. In how many regions can this planar graph be partitioned?
asked
Mar 28
in
Graph Theory
by
srestha
Veteran
(
111k
points)

55
views
discretemathematics
0
votes
0
answers
15
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
in
Graph Theory
by
noxevolution
(
93
points)

32
views
graphtheory
0
votes
0
answers
16
Narsingh deo
What is meant by edge disjoint hamiltonian circuits in a graph
asked
Mar 5
in
Graph Theory
by
Winner
(
249
points)

59
views
graphtheory
+1
vote
0
answers
17
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
in
Graph Theory
by
Sayan Bose
Loyal
(
6.9k
points)

81
views
jest
graphtheory
0
votes
0
answers
18
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
Feb 17
in
Graph Theory
by
dan31
Junior
(
823
points)

82
views
jest
2019
discretemathematics
0
votes
0
answers
19
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
Feb 17
in
Graph Theory
by
dan31
Junior
(
823
points)

54
views
jest
2019
discretemathematics
+4
votes
8
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
in
Graph Theory
by
Arjun
Veteran
(
406k
points)

2.8k
views
gate2019
engineeringmathematics
discretemathematics
graphtheory
graphconnectivity
+2
votes
1
answer
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
in
Graph Theory
by
Arjun
Veteran
(
406k
points)

2.3k
views
gate2019
engineeringmathematics
discretemathematics
graphtheory
graphconnectivity
0
votes
2
answers
22
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
(
57
points)

743
views
0
votes
0
answers
23
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
(
1k
points)

41
views
+1
vote
0
answers
24
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
(
417
points)

118
views
graphmatching
discretemathematics
graphtheory
testseries
+1
vote
0
answers
25
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
(
4.4k
points)

32
views
0
votes
0
answers
26
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
Boss
(
10.1k
points)

71
views
0
votes
2
answers
27
#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
(
459
points)

88
views
graphtheory
0
votes
0
answers
28
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
(
1k
points)

97
views
mst
0
votes
0
answers
29
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
(
141
points)

60
views
0
votes
0
answers
30
Counting
asked
Jan 25
in
Graph Theory
by
screddy1313
(
455
points)

39
views
discretemathematics
graphtheory
engineeringmathematics
chromaticnumbers
#counting
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
The day that made me an IIScian :)
Unanswered Previous year GATE/TIFR questions
From being a Failure to getting into IISc  (Rank 888, Score 692)
My interview experience at IITs/IISc
IIT Delhi CSE Mtech interview 14 may
All categories
General Aptitude
1.8k
Engineering Mathematics
7.3k
Discrete Mathematics
5.1k
Mathematical Logic
2.1k
Set Theory & Algebra
1.3k
Combinatory
874
Graph Theory
803
Probability
992
Linear Algebra
689
Calculus
488
Digital Logic
2.9k
Programming & DS
4.9k
Algorithms
4.3k
Theory of Computation
6k
Compiler Design
2.1k
Operating System
4.2k
Databases
4.1k
CO & Architecture
3.4k
Computer Networks
4.1k
Non GATE
1.4k
Others
1.4k
Admissions
596
Exam Queries
577
Tier 1 Placement Questions
23
Job Queries
72
Projects
18
Follow @csegate
Recent questions in Graph Theory
Recent Blog Comments
@Debargh, Yes. 👍
Thanks. Regarding the probability question, was...
Thanks
What were the Eigen values of A apart from 0? I...
49,540
questions
54,099
answers
187,267
comments
71,006
users