menu
search
Log In
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 questions tagged graph-theory

0 votes
1 answer 19 views
ACE Discrete Maths Text Book; Graph Theory; Page 100, question 18.
A tree has 14 vertices of degree 1 and degree of each of remaining vertices is 4 or 5. If the tree has ‘n’ vertices then number of vertices with degree 5 is:- (40-2n) (3n-54) (54-2n) (3n-40)
asked Jul 14 in Graph Theory subhashchaganti 5 points 19 views
0 votes
1 answer 20 views
Self-Doubt Graph theory book Rosen or Narsingh Deo
Hi There is 2 book for graph theory so which book is followed because is rosen is short for graph theory and deo is very detailed so for gate which book is followed ? in rosen so there is complete detail for graph theory so if i read rosen so can i make gate related questions or not ? thank you
asked Jun 30 in Graph Theory ykrishnay 103 points 20 views
0 votes
0 answers 15 views
graph theory
On a gate paper 2015 set 2 Q26 CS of 2 marks theres a question about self complementary graph, what is the meaning of congruent to 0 mod 4, 1 mod 4
On a gate paper 2015 set 2 Q26 CS of 2 marks theres a question about self complementary graph, what is the meaning of congruent to 0 mod 4, 1 mod 4
asked Jun 26 in Mathematical Logic Chama hage 5 points 15 views
0 votes
0 answers 22 views
Kenneth Rosen Exercise 10.4 question 25 Graph Connectivity
Find the number of paths of length n between any two nonadjacent vertices in K3,3 for the following values of n: a)2 b)3. c)4. d)5 ( i am able to understand the number of paths of length n between any two adjacent vertices in K3,3… but i am not able to get intuition for non adjacent in the adjacency matrix)
asked Apr 26 in Graph Theory ami_c05 5 points 22 views
1 vote
0 answers 24 views
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
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 donniedarko 39 points 24 views
0 votes
1 answer 30 views
Dominating set and Independent set.
Please explain the basic difference between Independent set and Dominating Set?
Please explain the basic difference between Independent set and Dominating Set?
asked Feb 21 in Graph Theory arpit_18 5 points 30 views
0 votes
0 answers 16 views
BOOKNAME : GRAPH THEORY, CHAPTER: CONNECTEDNESS COMPLETE, REGULAR AND BIPARTITE GRAPHS
If G is a connected graph containing a cycle c which contains an edge e , then show that G-e is still connected.
asked Feb 20 in Study Resources chssktejaswini 5 points 16 views
1 vote
2 answers 677 views
GATE CSE 2021 Set 1 | Question: 16 | Video Solution
In an undirected connected planar graph $G$, there are eight vertices and five faces. The number of edges in $G$ is _________.
asked Feb 18 in Graph Theory Arjun 1.5k points 677 views
3 votes
2 answers 711 views
GATE CSE 2021 Set 1 | Question: 36 | Video Solution
Let $G=(V, E)$ be an undirected unweighted connected graph. The diameter of $G$ is defined as: $\text{diam}(G)=\displaystyle \max_{u,v\in V} \{\text{the length of shortest path between $u$ and $v$}\}$ Let $M$ be the adjacency matrix of $G$. Define graph $G_2$ on the same set of ... $\text{diam}(G_2) = \text{diam}(G)$ $\text{diam}(G)< \text{diam}(G_2)\leq 2\; \text{diam}(G)$
asked Feb 18 in Graph Theory Arjun 1.5k points 711 views
1 vote
1 answer 35 views
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)
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 Satish Chandra 9 points 35 views
0 votes
2 answers 54 views
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
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 wander 301 points 54 views
1 vote
1 answer 87 views
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 .
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 agastya_08 11 points 87 views
1 vote
1 answer 78 views
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?
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 least $\frac{n}{2}$ 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 KUSHAGRA गुप्ता 1.4k points 78 views
0 votes
1 answer 48 views
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
$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$ $5-10+r=2$ $r=7$ Now ... $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 KUSHAGRA गुप्ता 1.4k points 48 views
0 votes
4 answers 82 views
#DM #Graphs labeled simple graphs
How to count number of labeled simple graphs? Please explain!
How to count number of labeled simple graphs? Please explain!
asked Aug 16, 2020 in Graph Theory mamtuj -25 points 82 views
0 votes
0 answers 24 views
Textbook questions #doubt
What should be the answer?
What should be the answer?
asked Jul 22, 2020 in Graph Theory premu 163 points 24 views
0 votes
1 answer 86 views
Graph Theory with Applications to Engineering and Computer Science, Narsingh Deo, Chapter 4 Question 27
I was working from the famous book of Deo. Then i found this problem very hard and interesting. Any ideas to give me? - Let us define a new term called edge isomorphism as follows: Two graphs G1 and G2 are edge isomorphic if there is a one-to- ... are also incident in G2. Discuss the properties of edge isomorphism. Construct an example to prove that edge-isomorphic graphs may not be isomorphic.
asked Jun 23, 2020 in Graph Theory dararirum 5 points 86 views
0 votes
1 answer 86 views
Graph Theory with Applications to Engineering and Computer Science, Narsingh Deo, Chapter 2 Question 21
From Narsingh Deo, Graph Theory -> A round-robin tournament (when every player plays against every other) among n players (n being an even number) can be represented by a complete graph of n vertices. Discuss how you would schedule the tournaments to finish in the shortest possible time.
asked Jun 23, 2020 in Others dararirum 5 points 86 views
0 votes
1 answer 40 views
Self doubt GRAPH THEORY
asked May 31, 2020 in Graph Theory Abhipsa 17 points 40 views
0 votes
1 answer 136 views
Find no of Hamiltonian cycles in kn,n
How many Hamiltonian cycles are there in complete bipartite graph K n,n
How many Hamiltonian cycles are there in complete bipartite graph K n,n
asked May 9, 2020 in Graph Theory SANDEEP1729 5 points 136 views
0 votes
1 answer 37 views
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
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 Abhipsa 17 points 37 views
0 votes
1 answer 27 views
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
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 Abhipsa 17 points 27 views
0 votes
0 answers 47 views
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?
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 Abhipsa 17 points 47 views
1 vote
0 answers 133 views
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)
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 highest degree (I am assuming ... ? (Also 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 nilotpola 9 points 133 views
0 votes
0 answers 31 views
Graph theory 3-Ordered trees possible for a given no of nodes
The number of possible 3-ordered trees with 5 nodes A,B,C,D,E is ??
asked Apr 28, 2020 in Graph Theory ramcharantej_24 13 points 31 views
0 votes
1 answer 34 views
Number of perfect matching in Kn?
Find number of perfect matching in Kn where n is even? Please explain too?
Find number of perfect matching in Kn where n is even? Please explain too?
asked Apr 23, 2020 in Graph Theory darshansharma_ 5 points 34 views
0 votes
1 answer 50 views
Why Euler circuit does not exist when number of odd degree vertices is 2
Euler circuit does not exist if no of odd degree vertices is 2 in graph. Why so? And not even Euler path when number of odd degree vertices is 4. Why so?
asked Apr 23, 2020 in Graph Theory darshansharma_ 5 points 50 views
0 votes
1 answer 21 views
What is the degree of region?
What is the degree of region r4? How you find it?
What is the degree of region r4? How you find it?
asked Apr 22, 2020 in Graph Theory darshansharma_ 5 points 21 views
0 votes
0 answers 22 views
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$
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 admin 573 points 22 views
0 votes
0 answers 10 views
GATE1994-1.6, ISRO2008-29 Video Solution
The number of distinct simple graphs with up to three nodes is $15$ $10$ $7$ $9$
The number of distinct simple graphs with up to three nodes is $15$ $10$ $7$ $9$
asked Apr 18, 2020 in Graph Theory admin 573 points 10 views
0 votes
0 answers 16 views
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______.
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 admin 573 points 16 views
0 votes
0 answers 13 views
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
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 between two nodes ... $\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 admin 573 points 13 views
0 votes
0 answers 13 views
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
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 admin 573 points 13 views
0 votes
0 answers 22 views
GATE2002-1.25, ISRO2008-30, ISRO2016-6 Video Solution
The maximum number of edges in a n-node undirected graph without self loops is $n^2$ $\frac{n(n-1)}{2}$ $n-1$ $\frac{(n+1)(n)}{2}$
asked Apr 18, 2020 in Graph Theory admin 573 points 22 views
0 votes
0 answers 11 views
GATE2003-36 Video Solution
How many perfect matching are there in a complete graph of $6$ vertices? $15$ $24$ $30$ $60$
How many perfect matching are there in a complete graph of $6$ vertices? $15$ $24$ $30$ $60$
asked Apr 18, 2020 in Graph Theory admin 573 points 11 views
0 votes
0 answers 10 views
GATE2016-2-03 Video Solution
The minimum number of colours that is sufficient to vertex-colour any planar graph is ________.
The minimum number of colours that is sufficient to vertex-colour any planar graph is ________.
asked Apr 18, 2020 in Graph Theory admin 573 points 10 views
0 votes
0 answers 14 views
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$
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 admin 573 points 14 views
0 votes
0 answers 16 views
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$
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 admin 573 points 16 views
0 votes
0 answers 10 views
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
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 admin 573 points 10 views
Page:
Dark theme
Muffin by Hélio Chun
Thanks to Q2A
...