Recent questions and answers in Graph Theory - GATE CSE Doubts

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 Havel-Hakimi 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

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

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 1-2-3 and 2-3-1 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

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

+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

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

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

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

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 Np-Complete 2. Np-Complete 3. NP but not Np-Complete 4. None of the above

asked Dec 28, 2019 in Graph Theory by Chirag Shilwant (179 points) | 11 views

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

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

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

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

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

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 (n-1)*(n-2)/2 +1 https://cs.stackexchange.com/questions/7373/how-many-edges-must-a-graph-with-n-vertices-have-in-order-to-guarantee-that- ... 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

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

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

0 votes

1 answer

Applied Course test series: Graph theory
Maximum no. of edges in triangle-free , 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

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

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

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 1-2-3-1 or 1-3-2-1 or 2-3-1-2 or ... 3-1-2-3 or 3-2-1-3. 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

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

+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

0 votes

1 answer

#discrete math
How many simple non-ismorphic trees pairwise are possible with 5 vertices

answered Nov 27, 2019 in Graph Theory by Kushagra गुप्ता (176 points) | 13 views

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

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

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

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 ( n-k \right )\left ( n-k+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

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

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

0 votes

1 answer

GATE GURU: GRAPH THEORY

answered Oct 21, 2019 in Graph Theory by GAITONDE (1.7k points) | 34 views

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

To see more, click for all the questions in this category.

Recent questions and answers in Graph Theory

3,314 questions

1,581 answers

10,271 comments

89,904 users