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
Blogs
Previous Year
Exams
Recent questions tagged graph-theory
+1
vote
0
answers
GATE graph theory
How many non-isomorphic graphs are possible with 6 edges 6 vertices each having a degree of 2? 2 4 5 6
asked
Mar 9
in
Graph Theory
by
donniedarko
(
39
points)
|
16
views
graph-theory
selfdoubt
0
votes
1
answer
Dominating set and Independent set.
Please explain the basic difference between Independent set and Dominating Set?
asked
Feb 21
in
Graph Theory
by
arpit_18
(
5
points)
|
16
views
graph-theory
discrete-maths
0
votes
0
answers
BOOKNAME : GRAPH THEORY, CHAPTER: CONNECTEDNESS COMPLETE, REGULAR AND BIPARTITE GRAPHS
asked
Feb 20
in
Study Resources
by
chssktejaswini
(
5
points)
|
9
views
graph-theory
+1
vote
1
answer
Ace Test Series
consider a cycle graph of 4 vertices and needs to perform the vertex coloring using 4 colors. The maximum number of vertex colorings possible is (Answer given as 68)
asked
Jan 24
in
Graph Theory
by
Satish Chandra
(
9
points)
|
24
views
graph-theory
0
votes
1
answer
What is total number of planer graph can be formed with 6 vertices ?
asked
Jan 11
in
Graph Theory
by
subhadip997
(
9
points)
|
38
views
graph-theory
discrete-maths
0
votes
2
answers
ACE test Series
Suppose that a tree T has N1 vertices of degree 1, 2 vertices of degree 2 , 4 vertices of degree 3 And 3 vertices of degree 4. Number of vertices in the tree is ? Answer given is 21
asked
Dec 22, 2020
in
DS
by
wander
(
301
points)
|
38
views
graphs
graph-theory
+1
vote
1
answer
Made easy test series
is this statement true? in a graph with unique edge weight the spanning tree of second lowest weight is unique. I am not not able to come up with the example to prove it wrong .
asked
Oct 30, 2020
in
Algorithms
by
agastya_08
(
11
points)
|
64
views
algorithms
spanning-tree
graph-theory
mst
+1
vote
1
answer
Self doubt - Graph Connectivity (NPTEL & PY)
Let G be a graph with n vertices and if every vertex has a degree of at least $\frac{n−1}{2}$ then G is connected. Source : https://gateoverflow.in/1221/gate2007-23 Let G be a graph with n vertices and if every vertex has a degree of at ... then G is connected. source : https://nptel.ac.in/courses/106/106/106106183/ My doubt : Which one is right?
asked
Sep 17, 2020
in
Graph Theory
by
KUSHAGRA गुप्ता
(
1.4k
points)
|
54
views
discrete-maths
graph-theory
0
votes
1
answer
Self Doubt - Planar graph (PY)
$K_5$ is non-planar. I am showing you my proof. Please tell me whether this is the right way or not to prove that $K_5$ is non-planar. $\sum$ (deg)$=4+4+4+4+4=20$ $e=10$ and $n=5$ Assume $K_5$ is planar. $v-e+r=2$ ... $K_5$ is non-planar. If this is the right way, why this method didn't work in this graph. Source: https://gateoverflow.in/87129/gate1990-3-vi
asked
Sep 15, 2020
in
Graph Theory
by
KUSHAGRA गुप्ता
(
1.4k
points)
|
36
views
discrete-maths
graph-planarity
graph-theory
self-doubt
0
votes
4
answers
#DM #Graphs labeled simple graphs
How to count number of labeled simple graphs? Please explain!
asked
Aug 16, 2020
in
Graph Theory
by
mamtuj
(
-25
points)
|
75
views
selfdoubt
graph-theory
graph
0
votes
0
answers
Textbook questions #doubt
What should be the answer?
asked
Jul 22, 2020
in
Graph Theory
by
premu
(
163
points)
|
20
views
graph-theory
0
votes
1
answer
Graph Theory with Applications to Engineering and Computer Science, Narsingh Deo, Chapter 4 Question 27
asked
Jun 23, 2020
in
Graph Theory
by
dararirum
(
5
points)
|
60
views
discrete-maths
graph-theory
graph-isomorphism
0
votes
1
answer
Graph Theory with Applications to Engineering and Computer Science, Narsingh Deo, Chapter 2 Question 21
asked
Jun 23, 2020
in
Others
by
dararirum
(
5
points)
|
57
views
discrete-maths
graph-theory
0
votes
1
answer
Self doubt GRAPH THEORY
asked
May 31, 2020
in
Graph Theory
by
Abhipsa
(
17
points)
|
32
views
graph-theory
discrete-mathematics
discrete-maths
discrete-maths
0
votes
1
answer
Find no of Hamiltonian cycles in kn,n
How many Hamiltonian cycles are there in complete bipartite graph K n,n
asked
May 9, 2020
in
Graph Theory
by
SANDEEP1729
(
5
points)
|
43
views
hamiltonian-graph
graph-theory
combinatory
0
votes
1
answer
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, 2020
in
Graph Theory
by
Abhipsa
(
17
points)
|
26
views
graph
trees
graph-theory
0
votes
1
answer
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, 2020
in
Graph Theory
by
Abhipsa
(
17
points)
|
21
views
graph-theory
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, 2020
in
Graph Theory
by
Abhipsa
(
17
points)
|
34
views
discrete-maths
graph-theory
+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 4, 2020
in
Mathematical Logic
by
nilotpola
(
9
points)
|
98
views
discrete-maths
graph-theory
graph
0
votes
0
answers
Graph theory 3-Ordered trees possible for a given no of nodes
asked
Apr 28, 2020
in
Graph Theory
by
ramcharantej_24
(
13
points)
|
25
views
trees
combinatory
graph-theory
discrete-maths
graph
0
votes
1
answer
Number of perfect matching in Kn?
Find number of perfect matching in Kn where n is even? Please explain too?
asked
Apr 23, 2020
in
Graph Theory
by
darshansharma_
(
5
points)
|
23
views
discrete-maths
graph-theory
0
votes
1
answer
Why Euler circuit does not exist when number of odd degree vertices is 2
asked
Apr 23, 2020
in
Graph Theory
by
darshansharma_
(
5
points)
|
37
views
discrete-maths
graph-theory
0
votes
1
answer
What is the degree of region?
What is the degree of region r4? How you find it?
asked
Apr 22, 2020
in
Graph Theory
by
darshansharma_
(
5
points)
|
14
views
graph-theory
discrete-maths
0
votes
0
answers
GATE2012-38 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 18, 2020
in
Graph Theory
by
admin
(
573
points)
|
18
views
gate2012
graph-theory
normal
marks-to-all
counting
video-solution
0
votes
0
answers
GATE1994-1.6, ISRO2008-29 Video Solution
The number of distinct simple graphs with up to three nodes is $15$ $10$ $7$ $9$
asked
Apr 18, 2020
in
Graph Theory
by
admin
(
573
points)
|
7
views
gate1994
graph-theory
combinatory
normal
isro2008
counting
video-solution
0
votes
0
answers
GATE2014-1-51 Video Solution
Consider an undirected graph $G$ where self-loops 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 $|a-c| \leq 1$ and $|b-d| \leq 1$. The number of edges in this graph is______.
asked
Apr 18, 2020
in
Graph Theory
by
admin
(
573
points)
|
11
views
gate2014-1
graph-theory
numerical-answers
normal
graph-connectivity
video-solution
0
votes
0
answers
GATE2018-30 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 i-j \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 18, 2020
in
Graph Theory
by
admin
(
573
points)
|
8
views
gate2018
graph-theory
graph-search
normal
video-solution
0
votes
0
answers
GATE2007-23 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 18, 2020
in
Graph Theory
by
admin
(
573
points)
|
10
views
gate2007
graph-theory
normal
graph-connectivity
video-solution
0
votes
0
answers
GATE2002-1.25, ISRO2008-30, ISRO2016-6 Video Solution
asked
Apr 18, 2020
in
Graph Theory
by
admin
(
573
points)
|
16
views
gate2002
graph-theory
easy
isro2008
isro2016
graph-connectivity
video-solution
0
votes
0
answers
GATE2003-36 Video Solution
How many perfect matching are there in a complete graph of $6$ vertices? $15$ $24$ $30$ $60$
asked
Apr 18, 2020
in
Graph Theory
by
admin
(
573
points)
|
7
views
gate2003
graph-theory
graph-matching
normal
video-solution
0
votes
0
answers
GATE2016-2-03 Video Solution
The minimum number of colours that is sufficient to vertex-colour any planar graph is ________.
asked
Apr 18, 2020
in
Graph Theory
by
admin
(
573
points)
|
7
views
gate2016-2
graph-theory
graph-coloring
normal
numerical-answers
video-solution
0
votes
0
answers
GATE2006-71 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 18, 2020
in
Graph Theory
by
admin
(
573
points)
|
10
views
gate2006
graph-theory
normal
degree-of-graph
video-solution
0
votes
0
answers
GATE2007-IT-25 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 18, 2020
in
Graph Theory
by
admin
(
573
points)
|
12
views
gate2007-it
graph-theory
spanning-tree
normal
video-solution
0
votes
0
answers
GATE1995-1.25 Video Solution
The minimum number of edges in a connected cyclic graph on $n$ vertices is: $n-1$ $n$ $n+1$ None of the above
asked
Apr 18, 2020
in
Graph Theory
by
admin
(
573
points)
|
7
views
gate1995
graph-theory
graph-connectivity
easy
video-solution
0
votes
0
answers
GATE2014-3-51 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$ $n-k$ $n-k+1$
asked
Apr 18, 2020
in
Graph Theory
by
admin
(
573
points)
|
16
views
gate2014-3
graph-theory
graph-connectivity
normal
video-solution
0
votes
0
answers
GATE2010-28 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 18, 2020
in
Graph Theory
by
admin
(
573
points)
|
12
views
gate2010
graph-theory
degree-of-graph
video-solution
0
votes
0
answers
GATE2006-72 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^{n-2}$ $2^{n-3}\times 3$ $2^{n-1}$
asked
Apr 18, 2020
in
Graph Theory
by
admin
(
573
points)
|
6
views
gate2006
graph-theory
normal
degree-of-graph
video-solution
0
votes
0
answers
GATE1994-2.5 Video Solution
The number of edges in a regular graph of degree $d$ and $n$ vertices is ____________
asked
Apr 18, 2020
in
Graph Theory
by
admin
(
573
points)
|
9
views
gate1994
graph-theory
easy
graph-connectivity
descriptive
video-solution
0
votes
0
answers
GATE2014-2-3 Video Solution
The maximum number of edges in a bipartite graph on $12$ vertices is____
asked
Apr 18, 2020
in
Graph Theory
by
admin
(
573
points)
|
8
views
gate2014-2
graph-theory
graph-connectivity
numerical-answers
normal
video-solution
0
votes
0
answers
GATE2017-2-23 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 18, 2020
in
Graph Theory
by
admin
(
573
points)
|
13
views
gate2017-2
graph-theory
numerical-answers
degree-of-graph
video-solution
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.
Recent Posts
New GATEOverflow PDFs
Guidelines to users
No Recent Blog Comments
9,197
questions
3,182
answers
14,686
comments
96,162
users