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 and answers in Graph Theory
+13
votes
3
answers
1
ISI Entrance Exam MTech (CS)
Consider all possible trees with $n$ nodes. Let $k$ be the number of nodes with degree greater than $1$ in a given tree. What is the maximum possible value of $k$?
answered
1 day
ago
in
Graph Theory
by
rohith1001
(
155
points)

901
views
isi2016
graphtheory
trees
descriptive
+4
votes
2
answers
2
MadeEasy Test Series 2018: Graph Theory  Graph Coloring
answer given is 4. Please provide a detailed solution.
answered
Sep 3
in
Graph Theory
by
Rishav_Bhatt
(
117
points)

146
views
graphtheory
graphcoloring
madeeasytestseries
madeeasytestseries2018
0
votes
1
answer
3
CUTSET
answered
Sep 1
in
Graph Theory
by
Devvrat Tyagi
(
161
points)

54
views
+26
votes
6
answers
4
GATE2014251
A cycle on $n$ vertices is isomorphic to its complement. The value of $n$ is _____.
answered
Aug 21
in
Graph Theory
by
King Suleiman
Junior
(
735
points)

3.7k
views
gate20142
graphtheory
numericalanswers
normal
graphisomorphism
nongate
+1
vote
2
answers
5
Graph Connectivity
Consider the given statements S1: In a simple graph G with 6 vertices, if degree of each vertex is 2, then Euler circuit exists in G. S2:In a simple graph G, if degree of each vertex is 3 then the graph G is connected. Which of the following is/are true?
answered
Aug 5
in
Graph Theory
by
IamDRD
(
25
points)

206
views
graphtheory
eulergraph
graphconnectivity
+1
vote
2
answers
6
#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.
answered
Aug 1
in
Graph Theory
by
Raghava45
(
337
points)

88
views
discretemathematics
graphtheory
+1
vote
3
answers
7
UGCNETJune2015II5
Consider a Hamiltonian Graph(G) with no loops and parallel edges. Which of the following is true with respect to this graph (G)? deg (v) $\geq$ n/2 for each vertex of G $\mid E(G) \mid \geq $1/2 (n1)(n2)+2 edges deg(v) + deg(w) $\geq$ n fr every v and $\omega$ not connected by an edge a and b b and c a and c a, b, and c
answered
Aug 1
in
Graph Theory
by
tripu
(
11
points)

1.9k
views
ugcnetjune2015ii
discretemathematics
graphtheory
+1
vote
1
answer
8
UGCNETJune2019II69
Consider the following properties with respect to a flow network $G=(V,E)$ in which a flow is a realvalued function $f:V \times V \rightarrow R$: $P_1$: For all $u, v, \in V, \: f(u,v)=f(v,u)$ $P_2$: $\underset{v \in V}{\Sigma} f(u,v)=0$ for all $u \in V$ Which one of the following is/are correct? Only $P_1$ Only $P_2$ Both $P_1$ and $P_2$ Neither $P_1$ nor $P_2$
answered
Jul 29
in
Graph Theory
by
abhinav kumar
(
23
points)

45
views
ugcnetjune2019ii
flownetwork
+2
votes
3
answers
9
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$
answered
Jul 26
in
Graph Theory
by
gvjha3
(
11
points)

99
views
+1
vote
1
answer
10
graph theory(basic doubt)
Q.1)How many nonisomorphic simple graph are there with 6 vertices and 4 edges??
answered
Jul 24
in
Graph Theory
by
gorya506
(
173
points)

58
views
+36
votes
7
answers
11
GATE200340
A graph $G=(V,E)$ satisfies $\mid E \mid \leq 3 \mid V \mid  6$. The mindegree of $G$ is defined as $\min_{v\in V}\left\{ \text{degree }(v)\right \}$. Therefore, mindegree of $G$ cannot be $3$ $4$ $5$ $6$
answered
Jul 14
in
Graph Theory
by
PRANAV M
(
175
points)

3.5k
views
gate2003
graphtheory
normal
degreeofgraph
+39
votes
3
answers
12
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
Jul 5
in
Graph Theory
by
pritishc
(
215
points)

4k
views
gate2004
graphtheory
permutationandcombination
normal
counting
0
votes
1
answer
13
planar graph
Is this a planar graph ?
answered
Jul 4
in
Graph Theory
by
Peyush
(
11
points)

92
views
+3
votes
1
answer
14
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$
answered
Jul 3
in
Graph Theory
by
Satbir
Boss
(
18k
points)

100
views
ugcnetjune2019ii
graphtheory
+2
votes
1
answer
15
UGCNETJune2019II4
Suppose that a connected planar graph has six vertices, each of degree four. Into how many regions is the plane divided by a planar representation of this graph? $6$ $8$ $12$ $20$
answered
Jul 3
in
Graph Theory
by
Satbir
Boss
(
18k
points)

115
views
ugcnetjune2019ii
graphplanarity
handshakingtheorem
+33
votes
7
answers
16
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
Jun 25
in
Graph Theory
by
ankitrazzagmail.com
(
133
points)

4.3k
views
gate20143
graphtheory
graphconnectivity
normal
+1
vote
1
answer
17
Graph Coloring
How many ways are there to color this graph from any $4$ of the following colors : Violet, Indigo, Blue, Green, Yellow, Orange and Red ? There is a condition that adjacent vertices should not be of the same color I am getting $1680$. Is it correct?
answered
Jun 21
in
Graph Theory
by
Satbir
Boss
(
18k
points)

292
views
graphtheory
graphcoloring
permutationandcombination
0
votes
1
answer
18
Planar Graph
Can minimum degree of a planar graph be $5$? Give some example
answered
Jun 21
in
Graph Theory
by
Satbir
Boss
(
18k
points)

241
views
graphtheory
graphplanarity
+1
vote
1
answer
19
Doubt
How many distinct unlabeled graphs are there with 4 vertices and 3 edges?
answered
Jun 13
in
Graph Theory
by
Gyanu
Active
(
1.7k
points)

74
views
0
votes
1
answer
20
Zeal Test Series 2019: Graph Theory  Graph Connectivity
answered
Jun 12
in
Graph Theory
by
Gyanu
Active
(
1.7k
points)

99
views
zeal
graphtheory
graphconnectivity
zeal2019
+2
votes
3
answers
21
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? Vertex $n$ has degree $1$ Graph is connected There is a path from vertex $1$ to vertex $n$ Spanning tree will include edge connecting vertex $1$ and vertex $n$
answered
Jun 12
in
Graph Theory
by
Sainath Mandavilli
(
23
points)

120
views
discretemathematics
graphtheory
0
votes
2
answers
22
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.
answered
Jun 12
in
Graph Theory
by
Akanksha Agrawal
(
63
points)

78
views
graphtheory
+1
vote
1
answer
23
TIFR2019B12
Let $G=(V,E)$ be a directed graph with $n(\geq 2)$ vertices, including a special vertex $r$. Each edge $e \in E$ has a strictly positive edge weight $w(e)$. An arborescence in $G$ rooted at $r$ is a subgraph $H$ of $G$ in which every ... $w^*$ is less than the weight of the minimum weight directed Hamiltonian cycle in $G$, when $G$ has a directed Hamiltonian cycle
answered
Jun 8
in
Graph Theory
by
Arjun
Veteran
(
418k
points)

263
views
tifr2019
graphconnectivity
graphtheory
difficult
+2
votes
1
answer
24
GATE19879d
Specify an adjacencylists representation of the undirected graph given above.
answered
Jun 5
in
Graph Theory
by
Satbir
Boss
(
18k
points)

324
views
gate1987
graphtheory
easy
graphconnectivity
descriptive
0
votes
2
answers
25
#GRAPH THEORY
A simple regular graph n vertices and 24 edges, find all possible values of n.
answered
Jun 4
in
Graph Theory
by
rballiwal
Active
(
1.2k
points)

99
views
graphtheory
0
votes
1
answer
26
self doubt
What is the general formula for number of simple graph having n unlabelled vertices ??
answered
Jun 4
in
Graph Theory
by
rballiwal
Active
(
1.2k
points)

53
views
simplegraph
+2
votes
2
answers
27
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
answered
Jun 4
in
Graph Theory
by
rballiwal
Active
(
1.2k
points)

120
views
graphtheory
discretemathematics
0
votes
1
answer
28
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??
answered
Jun 4
in
Graph Theory
by
rballiwal
Active
(
1.2k
points)

22
views
graph
+2
votes
3
answers
29
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.
answered
Jun 4
in
Graph Theory
by
abhishekmehta4u
Boss
(
34.6k
points)

53
views
+1
vote
1
answer
30
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.
answered
Jun 4
in
Graph Theory
by
chandan2teja
(
131
points)

52
views
graphtheory
discretemathematics
+5
votes
8
answers
31
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}$
answered
Jun 3
in
Graph Theory
by
akshay96
(
11
points)

3k
views
gate2019
engineeringmathematics
discretemathematics
graphtheory
graphconnectivity
+1
vote
1
answer
32
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_____________
answered
May 23
in
Graph Theory
by
Satbir
Boss
(
18k
points)

100
views
madeeasytestseries
graphtheory
theoryofcomputation
+4
votes
0
answers
33
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
(
14.3k
points)

82
views
graphtheory
linearalgebra
+1
vote
2
answers
34
CMI2011B01b
A multinational company is developing an industrial area with many buildings. They want to connect the buildings with a set of roads so that: Each road connects exactly two buildings. Any two buildings are connected via a sequence of roads. ... preferred roads differing in at least one road? Substantiate your answers by either proving the assertion or providing a counterexample.
answered
May 19
in
Graph Theory
by
Arjun
Veteran
(
418k
points)

132
views
cmi2011
descriptive
graphtheory
graphconnectivity
+2
votes
2
answers
35
GATE19894vii
Provide short answers to the following questions: In the graph shown above, the depthfirst spanning tree edges are marked with a 'T'. Identify the forward, backward and cross edges.
answered
May 18
in
Graph Theory
by
Arjun
Veteran
(
418k
points)

290
views
gate1989
descriptive
graphtheory
spanningtree
dfs
+1
vote
0
answers
36
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.9k
points)

63
views
graphtheory
graphalgorithms
graphconnectivity
multistagegraph
directedacyclicgraph
dag
0
votes
0
answers
37
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
(
41.4k
points)

43
views
isi2017pcbb
engineeringmathematics
discretemathematics
graphtheory
descriptive
+20
votes
5
answers
38
TIFR2010B36
In a directed graph, every vertex has exactly seven edges coming in. What can one always say about the number of edges going out of its vertices? Exactly seven edges leave every vertex. Exactly seven edges leave some vertex. Some vertex has at least seven edges leaving it. The number of edges coming out of vertex is odd. None of the above.
answered
Mar 29
in
Graph Theory
by
Debargha Bhattacharj
Junior
(
597
points)

1.1k
views
tifr2010
graphtheory
degreeofgraph
0
votes
1
answer
39
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.
answered
Mar 29
in
Graph Theory
by
ankitgupta.1729
Boss
(
14.3k
points)

78
views
discretemathematics
+1
vote
1
answer
40
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?
answered
Mar 28
in
Graph Theory
by
abhishekmehta4u
Boss
(
34.6k
points)

59
views
discretemathematics
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
GATE 2020 Application Form Opened!
My GATE Preparation Journey
ISI MTECH CS 2019 INTERVIEW EXPERIENCE
IIT HYDERABAD MTECH TA INTERVIEW EXPERIENCE
How to prepare for GATE with a fulltime job??
All categories
General Aptitude
1.8k
Engineering Mathematics
7.3k
Discrete Mathematics
5.1k
Mathematical Logic
2.1k
Set Theory & Algebra
1.3k
Combinatory
879
Graph Theory
805
Probability
987
Linear Algebra
682
Calculus
489
Digital Logic
2.9k
Programming and DS
4.9k
Algorithms
4.4k
Theory of Computation
6.1k
Compiler Design
2.1k
Operating System
4.2k
Databases
4.1k
CO and Architecture
3.4k
Computer Networks
4.1k
Non GATE
1.5k
Others
1.6k
Admissions
595
Exam Queries
576
Tier 1 Placement Questions
23
Job Queries
72
Projects
17
Follow @csegate
Recent questions and answers in Graph Theory
Recent Blog Comments
will pdfs be uploaded ?
6th...
Sir
4th...
49,984
questions
55,138
answers
190,495
comments
85,159
users