Awesome q2a theme
Ask us anything
Toggle navigation
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Q&A
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous Year
Exams
Recent questions tagged graphtheory
0
votes
0
answers
Graph Theory with Applications to Engineering and Computer Science, Narsingh Deo, Chapter 4 Question 27
asked
Jun 24
in
Graph Theory
by
dararirum
(
7
points)

13
views
discrete_maths
graphtheory
graphisomorphism
0
votes
0
answers
Graph Theory with Applications to Engineering and Computer Science, Narsingh Deo, Chapter 2 Question 21
asked
Jun 23
in
Others
by
dararirum
(
7
points)

8
views
discrete_maths
graphtheory
0
votes
0
answers
Self doubt GRAPH THEORY
asked
May 31
in
Graph Theory
by
Abhipsa
(
27
points)

11
views
graphtheory
discretemathematics
#discrete_maths
discrete_maths
0
votes
0
answers
Find no of Hamiltonian cycles in kn,n
How many Hamiltonian cycles are there in complete bipartite graph K n,n
asked
May 9
in
Graph Theory
by
SANDEEP1729
(
7
points)

4
views
hamiltoniangraph
graphtheory
permutationandcombination
0
votes
0
answers
Trees self doubt
S1: A tree with n vertices which has no vertices of degree 2 must have at least leaves S2: The number of trees on 5 labelled vertices is 125. Which of the following statements is true? (A). Only S1 (B). Only S2 (C). Only S1 and S2 (D). None of the above
asked
May 8
in
Graph Theory
by
Abhipsa
(
27
points)

14
views
graph
trees
graphtheory
0
votes
0
answers
Hamiltonian Graph
Consider the following Graphs: S1: Graph with vertices and each vertex has degree S2: Graph with 20 vertices such that for every 2 vertices Which of the following represents hamilton graph? (A). Only S1 (B). Only S2 (C). Both S1 and S2 (D). Neither S1 nor S2
asked
May 8
in
Graph Theory
by
Abhipsa
(
27
points)

5
views
graphtheory
discrete_maths
0
votes
0
answers
Matching Number
Please tell me what is the Independence Number Domination Number Matching Number Covering Number of the given graph in the picture. Does perfect matching exist in the given graph?
asked
May 7
in
Graph Theory
by
Abhipsa
(
27
points)

15
views
discrete_maths
graphtheory
+1
vote
0
answers
Havell Hakimi Algorithm  Graph Theory
The Havell Hakimi Algorithm Requires the sorting of the degree sequence and later marking and subtracting according to that order. Does this means that the vertex with the highest degree will always have an edge with the vertex with the second ... I have noticed that without sorting the algorithm doesn't give correct output so I think it is a necessary step)
asked
May 5
in
Mathematical Logic
by
nilotpola
(
7
points)

29
views
discrete_maths
graphtheory
graph
0
votes
0
answers
Graph theory 3Ordered trees possible for a given no of nodes
asked
Apr 28
in
Graph Theory
by
ramcharantej_24
(
22
points)

7
views
trees
permutationandcombination
graphtheory
discrete_maths
graph
0
votes
0
answers
Number of perfect matching in Kn?
Find number of perfect matching in Kn where n is even? Please explain too?
asked
Apr 23
in
Graph Theory
by
darshansharma_
(
13
points)

4
views
discrete_maths
graphtheory
0
votes
0
answers
Why Euler circuit does not exist when number of odd degree vertices is 2
asked
Apr 23
in
Graph Theory
by
darshansharma_
(
13
points)

10
views
discrete_maths
graphtheory
#gatepreparation
0
votes
0
answers
What is the degree of region?
What is the degree of region r4? How you find it?
asked
Apr 22
in
Graph Theory
by
darshansharma_
(
13
points)

4
views
graphtheory
discrete_maths
0
votes
0
answers
GATE201238 Video Solution
Let $G$ be a complete undirected graph on $6$ vertices. If vertices of $G$ are labeled, then the number of distinct cycles of length $4$ in $G$ is equal to $15$ $30$ $90$ $360$
asked
Apr 19
in
Graph Theory
by
admin
(
3.6k
points)

2
views
gate2012
graphtheory
normal
markstoall
counting
videosolution
0
votes
0
answers
GATE19941.6, ISRO200829 Video Solution
The number of distinct simple graphs with up to three nodes is $15$ $10$ $7$ $9$
asked
Apr 19
in
Graph Theory
by
admin
(
3.6k
points)

1
view
gate1994
graphtheory
permutationandcombination
normal
isro2008
counting
videosolution
0
votes
0
answers
GATE2014151 Video Solution
Consider an undirected graph $G$ where selfloops are not allowed. The vertex set of $G$ is $\{(i,j) \mid1 \leq i \leq 12, 1 \leq j \leq 12\}$. There is an edge between $(a,b)$ and $(c,d)$ if $ac \leq 1$ and $bd \leq 1$. The number of edges in this graph is______.
asked
Apr 19
in
Graph Theory
by
admin
(
3.6k
points)

2
views
gate20141
graphtheory
numericalanswers
normal
graphconnectivity
videosolution
0
votes
0
answers
GATE201830 Video Solution
Let $G$ be a simple undirected graph. Let $T_D$ be a depth first search tree of $G$. Let $T_B$ be a breadth first search tree of $G$. Consider the following statements. No edge of $G$ is a cross edge with respect to $T_D$. (A cross edge in $G$ is ... $\mid ij \mid =1$. Which of the statements above must necessarily be true? I only II only Both I and II Neither I nor II
asked
Apr 19
in
Graph Theory
by
admin
(
3.6k
points)

2
views
gate2018
graphtheory
graphsearch
normal
videosolution
0
votes
0
answers
GATE200723 Video Solution
Which of the following graphs has an Eulerian circuit? Any $k$regular graph where $k$ is an even number. A complete graph on $90$ vertices. The complement of a cycle on $25$ vertices. None of the above
asked
Apr 19
in
Graph Theory
by
admin
(
3.6k
points)

3
views
gate2007
graphtheory
normal
graphconnectivity
videosolution
0
votes
0
answers
GATE20021.25, ISRO200830, ISRO20166 Video Solution
asked
Apr 19
in
Graph Theory
by
admin
(
3.6k
points)

8
views
gate2002
graphtheory
easy
isro2008
isro2016
graphconnectivity
videosolution
0
votes
0
answers
GATE200336 Video Solution
How many perfect matching are there in a complete graph of $6$ vertices? $15$ $24$ $30$ $60$
asked
Apr 19
in
Graph Theory
by
admin
(
3.6k
points)

1
view
gate2003
graphtheory
graphmatching
normal
videosolution
0
votes
0
answers
GATE2016203 Video Solution
The minimum number of colours that is sufficient to vertexcolour any planar graph is ________.
asked
Apr 19
in
Graph Theory
by
admin
(
3.6k
points)

2
views
gate20162
graphtheory
graphcoloring
normal
numericalanswers
videosolution
0
votes
0
answers
GATE200671 Video Solution
The $2^n$ vertices of a graph $G$ corresponds to all subsets of a set of size $n$, for $n \geq 6$. Two vertices of $G$ are adjacent if and only if the corresponding sets intersect in exactly two elements. The number of vertices of degree zero in $G$ is: $1$ $n$ $n + 1$ $2^n$
asked
Apr 19
in
Graph Theory
by
admin
(
3.6k
points)

2
views
gate2006
graphtheory
normal
degreeofgraph
videosolution
0
votes
0
answers
GATE2007IT25 Video Solution
What is the largest integer $m$ such that every simple connected graph with $n$ vertices and $n$ edges contains at least $m$ different spanning trees ? $1$ $2$ $3$ $n$
asked
Apr 19
in
Graph Theory
by
admin
(
3.6k
points)

1
view
gate2007it
graphtheory
spanningtree
normal
videosolution
0
votes
0
answers
GATE19951.25 Video Solution
The minimum number of edges in a connected cyclic graph on $n$ vertices is: $n1$ $n$ $n+1$ None of the above
asked
Apr 19
in
Graph Theory
by
admin
(
3.6k
points)

1
view
gate1995
graphtheory
graphconnectivity
easy
videosolution
0
votes
0
answers
GATE2014351 Video Solution
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$
asked
Apr 19
in
Graph Theory
by
admin
(
3.6k
points)

1
view
gate20143
graphtheory
graphconnectivity
normal
videosolution
0
votes
0
answers
GATE201028 Video Solution
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, 6, 5, 4, 4, 3, 2, 1$ $6, 6, 6, 6, 3, 3, 2, 2$ $7, 6, 6, 4, 4, 3, 2, 2$ $8, 7, 7, 6, 4, 2, 1, 1$ I and II III and IV IV only II and IV
asked
Apr 19
in
Graph Theory
by
admin
(
3.6k
points)

1
view
gate2010
graphtheory
degreeofgraph
videosolution
0
votes
0
answers
GATE200672 Video Solution
The $2^n$ vertices of a graph $G$ corresponds to all subsets of a set of size $n$, for $n \geq 6$. Two vertices of $G$ are adjacent if and only if the corresponding sets intersect in exactly two elements. The maximum degree of a vertex in $G$ is: $\binom{\frac{n}{2}}{2}.2^{\frac{n}{2}}$ $2^{n2}$ $2^{n3}\times 3$ $2^{n1}$
asked
Apr 19
in
Graph Theory
by
admin
(
3.6k
points)

2
views
gate2006
graphtheory
normal
degreeofgraph
videosolution
0
votes
0
answers
GATE19942.5 Video Solution
The number of edges in a regular graph of degree $d$ and $n$ vertices is ____________
asked
Apr 19
in
Graph Theory
by
admin
(
3.6k
points)

1
view
gate1994
graphtheory
easy
graphconnectivity
descriptive
videosolution
0
votes
0
answers
GATE201423 Video Solution
The maximum number of edges in a bipartite graph on $12$ vertices is____
asked
Apr 19
in
Graph Theory
by
admin
(
3.6k
points)

2
views
gate20142
graphtheory
graphconnectivity
numericalanswers
normal
videosolution
0
votes
0
answers
GATE2017223 Video Solution
$G$ is an undirected graph with $n$ vertices and $25$ edges such that each vertex of $G$ has degree at least $3$. Then the maximum possible value of $n$ is _________ .
asked
Apr 19
in
Graph Theory
by
admin
(
3.6k
points)

1
view
gate20172
graphtheory
numericalanswers
degreeofgraph
videosolution
0
votes
0
answers
GATE201326 Video Solution
The line graph $L(G)$ of a simple graph $G$ is defined as follows: There is exactly one vertex $v(e)$ in $L(G)$ for each edge $e$ in $G$. For any two edges $e$ and $e'$ in $G$, $L(G)$ has an edge between $v(e)$ and $v(e')$, if and only if $e$ and ... of a planar graph is planar. (S) The line graph of a tree is a tree. $P$ only $P$ and $R$ only $R$ only $P, Q$ and $S$ only
asked
Apr 19
in
Graph Theory
by
admin
(
3.6k
points)

1
view
gate2013
graphtheory
normal
linegraph
videosolution
0
votes
0
answers
GATE200479 Video Solution
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$
asked
Apr 19
in
Graph Theory
by
admin
(
3.6k
points)

2
views
gate2004
graphtheory
permutationandcombination
normal
counting
videosolution
0
votes
0
answers
GATE20038, ISRO200953 Video Solution
Let $G$ be an arbitrary graph with $n$ nodes and $k$ components. If a vertex is removed from $G$, the number of components in the resultant graph must necessarily lie down between $k$ and $n$ $k1$ and $k+1$ $k1$ and $n1$ $k+1$ and $nk$
asked
Apr 19
in
Graph Theory
by
admin
(
3.6k
points)

2
views
gate2003
graphtheory
graphconnectivity
normal
isro2009
videosolution
0
votes
0
answers
GATE201912 Video Solution
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
Apr 19
in
Graph Theory
by
admin
(
3.6k
points)

1
view
gate2019
engineeringmathematics
discretemathematics
graphtheory
graphconnectivity
videosolution
0
votes
0
answers
GATE201938 Video Solution
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
Apr 19
in
Graph Theory
by
admin
(
3.6k
points)

2
views
gate2019
engineeringmathematics
discretemathematics
graphtheory
graphconnectivity
videosolution
0
votes
0
answers
GATE20012.15 Video Solution
How many undirected graphs (not necessarily connected) can be constructed out of a given set $V=\{v_1, v_2, \dots v_n\}$ of $n$ vertices? $\frac{n(n1)} {2}$ $2^n$ $n!$ $2^\frac{n(n1)} {2} $
asked
Apr 19
in
Graph Theory
by
admin
(
3.6k
points)

1
view
gate2001
graphtheory
normal
counting
videosolution
0
votes
0
answers
GATE200340 Video Solution
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$
asked
Apr 19
in
Graph Theory
by
admin
(
3.6k
points)

1
view
gate2003
graphtheory
normal
degreeofgraph
videosolution
0
votes
0
answers
GATE2014251 Video Solution
A cycle on $n$ vertices is isomorphic to its complement. The value of $n$ is _____.
asked
Apr 19
in
Graph Theory
by
admin
(
3.6k
points)

1
view
gate20142
graphtheory
numericalanswers
normal
graphisomorphism
nongate
videosolution
0
votes
0
answers
GATE199101,xv Video Solution
The maximum number of possible edges in an undirected graph with $n$ vertices and $k$ components is ______.
asked
Apr 19
in
Graph Theory
by
admin
(
3.6k
points)

2
views
gate1991
graphtheory
graphconnectivity
normal
videosolution
0
votes
0
answers
GATE20092 Video Solution
What is the chromatic number of an $n$ vertex simple connected graph which does not contain any odd length cycle? Assume $n > 2$. $2$ $3$ $n1$ $n$
asked
Apr 19
in
Graph Theory
by
admin
(
3.6k
points)

4
views
gate2009
graphtheory
graphcoloring
normal
videosolution
0
votes
0
answers
GATE20101 Video Solution
Let $G=(V, E)$ be a graph. Define $\xi(G) = \sum\limits_d i_d*d$, where $i_d$ is the number of vertices of degree $d$ in $G.$ If $S$ and $T$ are two different trees with $\xi(S) = \xi(T)$, then $ S = 2 T $ $ S  =  T   1$ $ S =  T  $ $ S  =  T + 1$
asked
Apr 19
in
Graph Theory
by
admin
(
3.6k
points)

1
view
gate2010
graphtheory
normal
trees
videosolution
Page:
1
2
3
4
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
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Top Users
Jul 2020
bittujash
6 Points
RavGopal
4 Points
ankeshsingh
2 Points
prakhar123
1 Points
arpit_18
1 Points
pravincesingh
1 Points
Shaik Masthan
1 Points
srestha
1 Points
sameer2009
1 Points
7,525
questions
1,776
answers
10,835
comments
90,464
users