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 in Graph Theory
Recent
Hot!
Most votes
Most answers
Most views
Featured
Previous GATE
Recent
Hot!
Most votes
Most answers
Most views
Featured
Previous GATE
+2
votes
0
answers
MADE EASY TEST: BIPARTITE GRAPH
Maximum value of the minimum degree in a connected planar bipartite graph is ?
asked
6 days
ago
in
Graph Theory
by
Debapaul
(
613
points)

47
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?
asked
Jan 10
in
Graph Theory
by
Debapaul
(
613
points)

27
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]
asked
Jan 5
in
Graph Theory
by
shaktisingh
(
90
points)

24
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
(
117
points)

17
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
(
143
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)

51
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
(
117
points)

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

32
views
discrete_maths
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
asked
Dec 25, 2019
in
Graph Theory
by
haralk10
(
54
points)

40
views
graphtheory
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
(
117
points)

17
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
(
13
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
(
117
points)

33
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
(
407
points)

10
views
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.
asked
Dec 2, 2019
in
Graph Theory
by
Shivateja MST
(
96
points)

21
views
graphtheory
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
(
96
points)

9
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.
asked
Dec 1, 2019
in
Graph Theory
by
vishal burnwal
(
117
points)

24
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
(
96
points)

13
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
(
96
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
(
96
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.
asked
Nov 28, 2019
in
Graph Theory
by
Shivateja MST
(
96
points)

13
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
asked
Nov 27, 2019
in
Graph Theory
by
amit166
(
138
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.
asked
Nov 26, 2019
in
Graph Theory
by
DukeThunders
(
407
points)

23
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
(
613
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
(
729
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?
asked
Nov 2, 2019
in
Graph Theory
by
srestha
(
635
points)

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

37
views
graphtheory
graph
hamiltoniangraph
+1
vote
1
answer
GATE GURU: GRAPHS
asked
Oct 21, 2019
in
Graph Theory
by
Debapaul
(
613
points)

29
views
graphtheory
0
votes
1
answer
GATE GURU: GRAPH THEORY
asked
Oct 21, 2019
in
Graph Theory
by
Debapaul
(
613
points)

33
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
(
613
points)

17
views
discrete_maths
graphtheory
0
votes
1
answer
MADE EASY DISCRETE MATHS
Number of perfect matching in a complete graph of 5 vertices is _____ ANS should be 0 right? as when odd number of vertices are there we should have no matching right? But they have applied the matching formula and solved it. God knows why
asked
Oct 21, 2019
in
Graph Theory
by
Debapaul
(
613
points)

21
views
madeeasytestseries
discrete_maths
graphtheory
0
votes
0
answers
selfDoubt in edge formula for line graph
The line graph of a graph with nodes, edges, and vertex degrees contains nodes and edges (ref. Skiena 1990, p. 137) Question : does the no of edges in line graph(given below) got through e' formula is right? I am getting no of edges in ... 3 edges but it is 8 edges as we can see in the below line graph Please validate the edge formula of the line graph.
[closed]
asked
Oct 20, 2019
in
Graph Theory
by
shaktisingh
(
90
points)

20
views
graphtheory
linegraph
edges
graph
0
votes
0
answers
self doubt in no of regions in this graph
how to find regions in this graph manually?
asked
Oct 12, 2019
in
Graph Theory
by
shaktisingh
(
90
points)

11
views
graphtheory
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.
asked
Oct 2, 2019
in
Graph Theory
by
SuvasishDutta
(
152
points)

55
views
0
votes
0
answers
Hamiltonian path
How many Hamiltonian paths are there on the graph above(the graph is labelled)? 1 5 10 120
asked
Sep 10, 2019
in
Graph Theory
by
Lakshman Patel RJIT
(
110
points)

42
views
discrete_maths
graphtheory
hamiltonianpath
0
votes
0
answers
Made easy #graph theory
A graph is 3 connected and 4 line connected: True or false. 1) Removal of 2 vertex cannot disconnect the graph. 2)Removal of some 3 vertex can disconnect the graph.
asked
Sep 5, 2019
in
Graph Theory
by
kalra05
(
27
points)

15
views
#graphtheory
0
votes
0
answers
Self Doubt: Discrete Maths
asked
Sep 4, 2019
in
Graph Theory
by
GAITONDE
(
1.6k
points)

37
views
graphtheory
Page:
1
2
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
Jan 2020
shashin
1163 Points
Vimal Patel
306 Points
Deepakk Poonia (Dee)
305 Points
Debapaul
237 Points
Satbir
192 Points
SuvasishDutta
137 Points
Pratyush Priyam Kuan
118 Points
tp21
108 Points
DukeThunders
95 Points
pranay562
95 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
52
Engineering Mathematics
369
Discrete Mathematics
263
Mathematical Logic
113
Set Theory & Algebra
63
Combinatory
38
Graph Theory
49
Probability
38
Linear Algebra
36
Calculus
32
Digital Logic
188
Programming & DS
323
Algorithms
271
Theory of Computation
400
Compiler Design
188
Operating System
289
Databases
301
CO & Architecture
251
Computer Networks
249
Non GATE
4
Others
58
Admissions
11
Exam Queries
27
Tier 1 Placement Questions
2
Job Queries
4
Projects
1
Recent questions in Graph Theory
2,988
questions
1,509
answers
8,935
comments
89,814
users