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

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Exams
Recent questions and answers in Graph Theory
0
votes
0
answers
Made Easy: FLT Basic 3
Consider a degree sequence for n vertices. What is the worst case T.C to determine is a simple graph is possible with this degree sequence? In other words what is the TC of HavelHakimi procedure? $O(n^{2}$) $O(n^{2} log n$) $O(n$) $O(n log n$)
asked
Jan 26
in
Graph Theory
by
Sambhrant Maurya
(
396
points)

29
views
algorithms
graphtheory
0
votes
0
answers
Made Easy test series graph theory
A graph G with n vertices is said to be a void graph if and only if there’s no edge between any pair of vertices belonging to G. Let X be a void graph on 2^k + 1 vertices. Then if it is known that the minimum number of edge insertions required in the best case in order to make it connected is equal to 512, then the value of k^1/2 is equal ...
asked
Jan 25
in
Graph Theory
by
Ram Swaroop
(
173
points)

29
views
madeeasytestseries
discrete_maths
graphtheory
0
votes
0
answers
euler graphs
Suppose a connected graph of 15 vertices, given that it has a eulerian circuit, what is the minimum number of distinct euler circuits which it must have? NOTE: a circuit uses an ordered list of nodes, so a circuit with nodes 123 and 231 are distinct.
asked
Jan 21
in
Graph Theory
by
Vignaneswarkrishna
(
14
points)

14
views
0
votes
0
answers
Hamiltonian graphs
How many hamiltonian graphs possible for a complete graph of n vertices?
asked
Jan 21
in
Graph Theory
by
Vignaneswarkrishna
(
14
points)

19
views
0
votes
1
answer
Self doubtful : Discrete Maths
Every Kn,n is Hamilton graph. True or False?
answered
Jan 20
in
Graph Theory
by
Pratyush Priyam Kuan
(
803
points)

20
views
discrete_maths
graphtheory
hamiltoniangraph
0
votes
1
answer
Self doubt graph theory Hamilton graph
graph G which has a cut edge cannot be Hamiltonian ?
answered
Jan 19
in
Graph Theory
by
pranay562
(
926
points)

50
views
graphtheory
discrete_maths
+2
votes
0
answers
MADE EASY TEST: BIPARTITE GRAPH
Maximum value of the minimum degree in a connected planar bipartite graph is ?
asked
Jan 12
in
Graph Theory
by
Debapaul
(
698
points)

95
views
madeeasytestseries
graphtheory
discrete_maths
0
votes
1
answer
MADE EASY FLT: GRAPH THEORY
What is the $cardinality$ of the $largest$ $independent$ $set$ of this graph?
answered
Jan 10
in
Graph Theory
by
shashin
(
1.9k
points)

32
views
madeeasytestseries
graphtheory
0
votes
1
answer
doubt on statement of a simple graph
i was reading about simple graph there a statement is written The mean number of edges for graphs with vertices is given by , giving the sequence for , 2, ... of 0, 1/2, 3/2, 3, 5, 15/2, 21/2, 14, 18, .. explain this statement with an example? what is this mean number of edges?
[closed]
answered
Jan 6
in
Graph Theory
by
shashin
(
1.9k
points)

28
views
graphtheory
graph
0
votes
0
answers
Applied course test series : Graphs
In any connected ,undirected graph with exactly 5 simple cycles (that do not share any edges), there are atmost 10 simple paths between every pair of vertices. Whether the above given statement is true or false? Can someone explain above question?
asked
Jan 1
in
Graph Theory
by
vishal burnwal
(
135
points)

20
views
graph
0
votes
0
answers
Isomorphism self doubt
Whether 2 finite graph are isomorphic or not is a __________ problem (Assume P ! =NP) 1. NP Hard but not NpComplete 2. NpComplete 3. NP but not NpComplete 4. None of the above
asked
Dec 28, 2019
in
Graph Theory
by
Chirag Shilwant
(
179
points)

11
views
graphtheory
isomorphism
discrete_maths
computation
0
votes
0
answers
Applied GATE grand test 4  Graph theory
State true or False with explanation.
asked
Dec 26, 2019
in
Graph Theory
by
Satbir
(
4.1k
points)

53
views
graph
graphtheory
0
votes
0
answers
Made easy test series : Graph Theory
The number of labelled subgraph possible for the graph given below are ________ What will be the answer for above question? Because my answer is not matching with the test series answer.
asked
Dec 26, 2019
in
Graph Theory
by
vishal burnwal
(
135
points)

29
views
madeeasytestseries
0
votes
1
answer
Graph theory
Which of the following graphs are not bipartite? (a) I,II (b) I,II,III c) I,III d) II,III
answered
Dec 26, 2019
in
Graph Theory
by
Deepakk Poonia (Dee)
(
681
points)

43
views
graphtheory
0
votes
0
answers
Discrete Maths: Maximum number of edges in connected components
asked
Dec 25, 2019
in
Graph Theory
by
Debapaul
(
698
points)

32
views
discrete_maths
0
votes
0
answers
Gatebook Test series doubt
The edge graph of a graph G is the graph with vertex set E(G) in which two vertices are joined if and only if they are adjacent edges in G. if G is a simple graph with degree sequence , the no of edges in edge graph of G is?
asked
Dec 20, 2019
in
Graph Theory
by
Anirban Chand
(
16
points)

13
views
0
votes
0
answers
Applied course test series : Graph Theory
Given below are two statements: S1 : If a Graph G is n colorable then it's also n+1 colorable . S2 : Every Bipartite graph is 2 colorable Which of the above statement(s) is/are correct? Only S1 is false Only S2 is true Both S1 and S2 are true None of the above Plz can someone explain statement 1 and what will be the answer?
[closed]
asked
Dec 17, 2019
in
Graph Theory
by
vishal burnwal
(
135
points)

18
views
graph
theory
0
votes
0
answers
doubt in connected graph
How many edges must a graph with N vertices have in order to guarantee that it is connected? here on stack overflow they said (n1)*(n2)/2 +1 https://cs.stackexchange.com/questions/7373/howmanyedgesmustagraphwithnverticeshaveinordertoguaranteethat ... here we need just 21 edges for n=10 but according to given formula it is 9*8/2 + 1 = 37. so what is correct?
asked
Dec 9, 2019
in
Graph Theory
by
mehul vaidya
(
17
points)

9
views
0
votes
0
answers
Self Doubt : Graph Theory
How to know that a simple graph with given degree sequence {3,3,3,3,3,3,6} is hamiltonian or not.
asked
Dec 6, 2019
in
Graph Theory
by
vishal burnwal
(
135
points)

34
views
graphtheory
0
votes
1
answer
Graph thoery MCQ
Which of the following statements are true? If a simple graph G is not connected,then its complement G' is connected. If a simple graph G is connected,then its complement G' is not connected. A simple graph G with n vertices is necessarily ... simple graph has exactly two vertices of odd degree then there exists a path between two vertices of odd degree. Anyone please clarify.
answered
Dec 4, 2019
in
Graph Theory
by
amit166
(
138
points)

23
views
graphtheory
0
votes
0
answers
Self doubt degree of a node in a tree
What is the degree of the orange node? According to basic graph theory it should be 3. But somehwere in DS/algo I saw that it says degree of a node in a tree are only the number of children. So it should be 2?
asked
Dec 4, 2019
in
Graph Theory
by
DukeThunders
(
415
points)

10
views
0
votes
0
answers
Graph Theory Complement of Graph
If a Graph G have n vertices and all but one of odd degree,then no. of vertices of odd degree in G’ is ____ Assume G is a simple connected graph. Anyone please clarify.
asked
Dec 2, 2019
in
Graph Theory
by
Shivateja MST
(
108
points)

10
views
graphtheory
engineeringmaths
discrete_maths
0
votes
1
answer
Applied Course test series: Graph theory
Maximum no. of edges in trianglefree , simple planar graph with 10 vertices is _____ Plz give explaination and answer for above question.
answered
Dec 2, 2019
in
Graph Theory
by
chandrikabhuyan8
(
120
points)

25
views
graph
theory
0
votes
0
answers
Independent Set Vs Matching
Is the problem of Independent Set same as problem of finding Maximum matching of a Graph? Anyone please clarify with some example.
asked
Nov 30, 2019
in
Graph Theory
by
Shivateja MST
(
108
points)

14
views
discrete_maths
graphtheory
0
votes
0
answers
Mathematics Graph Theory doubt
It is given “A complete bipartite graph Km,n is planar iff m<=2 or n<=2” But it has to be m<=2 and n<=2 right? Anyone please clarify.
asked
Nov 29, 2019
in
Graph Theory
by
Shivateja MST
(
108
points)

21
views
graphtheory
engineeringmaths
discrete_maths
0
votes
0
answers
Hamiltonian cycles Graph Theory
Can anyone explain how to identify distinct Hamiltonian edge cycles in a graph with some example? Here distinct implies w.r.t structure or w.r.t order? Suppose if we consider K3, if we consider any order like 1231 or 1321 or 2312 or ... 3123 or 3213. All these have same structures and some are obtained by reversing some of the orders. Please clarify.
asked
Nov 29, 2019
in
Graph Theory
by
Shivateja MST
(
108
points)

11
views
graphtheory
hamiltoniangraph
engineeringmaths
discrete_maths
0
votes
1
answer
Mathematics Graph theory
How many simple graphs are possible with n vertices and m edges (m < C(n,2))? Anyone please clarify.
answered
Nov 28, 2019
in
Graph Theory
by
Satbir
(
4.1k
points)

14
views
graphtheory
engineeringmaths
discrete_maths
+1
vote
0
answers
# graph theory
Q.consider an undirected graph of eight vertices.The probability that there is an edge between a pair of vertices is 1/2 .what is the expected number of unordered cycle of length altest three
asked
Nov 28, 2019
in
Graph Theory
by
amit166
(
138
points)

21
views
graphtheory
0
votes
1
answer
#discrete math
How many simple nonismorphic trees pairwise are possible with 5 vertices
answered
Nov 27, 2019
in
Graph Theory
by
Kushagra गुप्ता
(
176
points)

13
views
engineeringmaths
0
votes
1
answer
ACE Test Series Compiler Test 57
My answer was A. To my understanding, I is true because if all edges have distinct weights then the lighest weight edge must be present in all the MSTs. II is false because if the heaviest edge acts as a connector then it has to be present in every MST else the graph won’t be connected. Please correct me if I’m wrong. Thank you.
answered
Nov 26, 2019
in
Graph Theory
by
GAITONDE
(
1.7k
points)

24
views
0
votes
0
answers
Self Doubt in Graph Theory  Subgraph topic
What is the difference between vertex induced subgraph and edge induced subgraph? Which one is the default case to be considered? Thanks!
asked
Nov 25, 2019
in
Graph Theory
by
Abhipsa Mishra
(
15
points)

15
views
graphtheory
0
votes
0
answers
GATE FORUM: MATHS
What is meant by $intersection$ of graphs? and how to find the $number$ $of$ $edges?$
asked
Nov 23, 2019
in
Graph Theory
by
Debapaul
(
698
points)

7
views
0
votes
0
answers
The Gate Academy test
What should be the answer?
asked
Nov 21, 2019
in
Graph Theory
by
Abhipsa Mishra
(
15
points)

16
views
graphtheory
discrete_maths
0
votes
0
answers
ACE Test series Discrete maths
The answer is given as 3. Someone, please explain the concept behind this question.
[closed]
asked
Nov 15, 2019
in
Graph Theory
by
Rudr Pawan
(
734
points)

10
views
discretemaths
0
votes
1
answer
ACE Test: Engineering Math
The maximum number of edges possible in a simple graph with $15$ vertices, and degree of each vertex is atmost $5$ is _______ My ans $55$, using $\frac{\left ( nk \right )\left ( nk+1 \right )}{2}$ and given ans $37$ using $degree\times V\geq 2E$ Which one correct?
answered
Nov 2, 2019
in
Graph Theory
by
Satbir
(
4.1k
points)

20
views
engineeringmaths
0
votes
1
answer
doubt on hamiltonian graph statement listed in mathworld.wolfram website
[closed]
answered
Oct 23, 2019
in
Graph Theory
by
Satbir
(
4.1k
points)

41
views
graphtheory
graph
hamiltoniangraph
0
votes
1
answer
MADE EASY: DISCRETE MATH SINGLE SUBJECT 2020
Let a graph G has 5 vertices and there are 3 vertices of degree 2 , one vertex of degree 1 and remaining vertex of degree 3. The complement of G is : Connected Disconnected Either A or B None of these Answer given is C. But my ... 4. But there is no degree 4 vertex mentioned in the question. Hence the complement of G must be connected. Please Check.
answered
Oct 22, 2019
in
Graph Theory
by
shaktisingh
(
90
points)

61
views
+1
vote
1
answer
GATE GURU: GRAPHS
answered
Oct 21, 2019
in
Graph Theory
by
GAITONDE
(
1.7k
points)

29
views
graphtheory
0
votes
1
answer
GATE GURU: GRAPH THEORY
answered
Oct 21, 2019
in
Graph Theory
by
GAITONDE
(
1.7k
points)

34
views
engineeringmaths
0
votes
0
answers
Self Doubt: Discrete Maths 101
Does Euler graph must contain Euler path? Is the converse true?
asked
Oct 21, 2019
in
Graph Theory
by
Debapaul
(
698
points)

17
views
discrete_maths
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
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Top Users
Feb 2020
shashin
363 Points
Shaik Masthan
79 Points
SuvasishDutta
39 Points
srestha
33 Points
Mk Utkarsh
32 Points
neeraj_bhatt
31 Points
!KARAN
30 Points
Debapaul
23 Points
Pratyush Priyam Kuan
18 Points
kalra05
18 Points
Monthly Top User and those within 60% of his/her points will get a share of monthly revenue of GO subject to a minimum payout of Rs. 500. Current monthly budget for Top Users is Rs. 75.
All categories
General Aptitude
62
Engineering Mathematics
423
Discrete Mathematics
304
Mathematical Logic
131
Set Theory & Algebra
71
Combinatory
47
Graph Theory
55
Probability
43
Linear Algebra
41
Calculus
35
Digital Logic
203
Programming & DS
350
Algorithms
298
Theory of Computation
443
Compiler Design
215
Operating System
310
Databases
324
CO & Architecture
279
Computer Networks
276
Non GATE
5
Others
66
Admissions
21
Exam Queries
32
Tier 1 Placement Questions
2
Job Queries
4
Projects
1
Recent questions and answers in Graph Theory
3,314
questions
1,581
answers
10,271
comments
89,904
users