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
+35
votes
7
answers
1
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
3 days
ago
in
Graph Theory
by
PRANAV M
(
129
points)

3.4k
views
gate2003
graphtheory
normal
degreeofgraph
+38
votes
3
answers
2
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
(
81
points)

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

88
views
+1
vote
1
answer
4
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
(
15.3k
points)

43
views
ugcnetjune2019ii
graphtheory
+1
vote
1
answer
5
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
(
15.3k
points)

63
views
ugcnetjune2019ii
graphplanarity
handshakingtheorem
0
votes
0
answers
6
UGCNETJune2019II69
asked
Jul 2
in
Graph Theory
by
Arjun
Veteran
(
413k
points)

14
views
ugcnetjune2019ii
flownetwork
+32
votes
7
answers
7
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
(
91
points)

4.2k
views
gate20143
graphtheory
graphconnectivity
normal
+1
vote
1
answer
8
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
(
15.3k
points)

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

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

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

88
views
zeal
graphtheory
graphconnectivity
zeal2019
+2
votes
3
answers
12
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)

115
views
discretemathematics
graphtheory
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.
answered
Jun 12
in
Graph Theory
by
Akanksha Agrawal
(
37
points)

70
views
graphtheory
+1
vote
1
answer
14
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
(
413k
points)

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

304
views
gate1987
graphtheory
easy
graphconnectivity
descriptive
0
votes
2
answers
16
#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)

95
views
graphtheory
+1
vote
1
answer
17
#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
Jun 4
in
Graph Theory
by
chandan2teja
(
127
points)

41
views
discretemathematics
graphtheory
0
votes
1
answer
18
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)

52
views
simplegraph
+2
votes
2
answers
19
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)

108
views
graphtheory
discretemathematics
0
votes
1
answer
20
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
+1
vote
3
answers
21
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.2k
points)

45
views
+1
vote
1
answer
22
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
(
127
points)

43
views
graphtheory
discretemathematics
+4
votes
8
answers
23
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)

2.9k
views
gate2019
engineeringmathematics
discretemathematics
graphtheory
graphconnectivity
+2
votes
2
answers
24
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
May 28
in
Graph Theory
by
Deepakk Poonia (Dee)
Boss
(
25k
points)

84
views
+1
vote
1
answer
25
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
(
15.3k
points)

80
views
madeeasytestseries
graphtheory
theoryofcomputation
+3
votes
0
answers
26
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.7k
points)

77
views
graphtheory
linearalgebra
+1
vote
2
answers
27
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
(
413k
points)

131
views
cmi2011
descriptive
graphtheory
graphconnectivity
+2
votes
2
answers
28
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
(
413k
points)

276
views
gate1989
descriptive
graphtheory
spanningtree
dfs
0
votes
0
answers
29
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)

54
views
graphtheory
graphalgorithms
graphconnectivity
multistagegraph
directedacyclicgraph
dag
0
votes
0
answers
30
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.9k
points)

41
views
isi2017pcbb
engineeringmathematics
discretemathematics
graphtheory
descriptive
+18
votes
5
answers
31
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
(
453
points)

1k
views
tifr2010
graphtheory
degreeofgraph
0
votes
1
answer
32
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
(
13.7k
points)

75
views
discretemathematics
+1
vote
1
answer
33
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.2k
points)

59
views
discretemathematics
+33
votes
5
answers
34
GATE2006IT25
Consider the undirected graph $G$ defined as follows. The vertices of $G$ are bit strings of length $n$. We have an edge between vertex $u$ and vertex $v$ if and only if $u$ and $v$ differ in exactly one bit position (in other words, $v$ can be obtained from $u$ by flipping a single ... $\left(\frac{1}{n}\right)$ $\left(\frac{2}{n}\right)$ $\left(\frac{3}{n}\right)$
answered
Mar 20
in
Graph Theory
by
Kuljeet Shan
Active
(
1.5k
points)

2.7k
views
gate2006it
graphtheory
graphcoloring
normal
0
votes
0
answers
35
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)

35
views
graphtheory
+1
vote
1
answer
36
Zeal Test Series 2019: Graph Theory  Graph Matching
answered
Mar 7
in
Graph Theory
by
abhishekmehta4u
Boss
(
34.2k
points)

85
views
zeal
discretemathematics
graphtheory
graphmatching
zeal2019
0
votes
0
answers
37
Narsingh deo
What is meant by edge disjoint hamiltonian circuits in a graph
asked
Mar 5
in
Graph Theory
by
Winner
(
249
points)

65
views
graphtheory
+1
vote
1
answer
38
Strongly Connected, Unilaterally connected and weakly Connected
Hi Guys, Is there any quick way of verifying Graph is Strongly Connected, Unilaterally connected and weakly Connected ? For Example  If 1 dead point then graph is Unilaterally Connected and If 2 dead points then graph is Weakly Connected.
answered
Feb 22
in
Graph Theory
by
saurav raghaw
Active
(
1.3k
points)

496
views
graphtheory
discretemathematics
algorithms
+2
votes
1
answer
39
GATE  2014  1 51 modified
Consider an directed graph G where selfloops are not allowed. The vertex set of G is {(i,j)∣1≤i≤12,1≤j≤12}There is an edge from(a,b) to (c,d) if a−c≤1 and b−d≤1. The number of edges in this graph is______
answered
Feb 18
in
Graph Theory
by
Priyadrasta Raut
(
373
points)

138
views
+1
vote
0
answers
40
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
(
7k
points)

87
views
jest
graphtheory
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
How to prepare for GATE with a fulltime job??
Interview Experience at IISc
All subject Gate notes from Standard Books!!
My journey from Wipro to an IISc student  GATE 2019
Interview Experience at IITPalakkad
All categories
General Aptitude
1.8k
Engineering Mathematics
7.3k
Discrete Mathematics
5.1k
Mathematical Logic
2.1k
Set Theory & Algebra
1.3k
Combinatory
880
Graph Theory
806
Probability
991
Linear Algebra
685
Calculus
489
Digital Logic
2.9k
Programming and DS
4.9k
Algorithms
4.4k
Theory of Computation
6k
Compiler Design
2.1k
Operating System
4.2k
Databases
4.1k
CO and Architecture
3.4k
Computer Networks
4.1k
Non GATE
1.4k
Others
1.5k
Admissions
594
Exam Queries
577
Tier 1 Placement Questions
23
Job Queries
72
Projects
18
Follow @csegate
Recent questions and answers in Graph Theory
Recent Blog Comments
Hi, the previous email was sent to only those who...
@kriti05 can you please tell me when did you got...
It was said that there will be an address...
sir .I recvd a mail which states "Your...
49,808
questions
54,489
answers
188,270
comments
74,680
users