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.
Top Users 2021 Aug 02 - 08
  1. SarathBaswa

    6 Points

Weekly Top User (excluding moderators) will get free access to GATE Overflow Test Series for GATE 2021
Recent questions and answers in Graph Theory

Recent questions and answers in 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)
answered Jul 15 in Graph Theory asqwer 633 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
answered Jul 10 in Graph Theory asqwer 633 points 20 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?
answered Feb 24 in Graph Theory Dheera -14 points 30 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
0 votes
0 answers 21 views
gate overflow book
https://gateoverflow.in/83854/gate1990-1-viii The above is the link of the question. In the solution it was assumed that the graph is complete. But in the question nothing is mentioned. Also a complete graph doesn't contain self loops. So what I'm thinking is, if we ... the number of the edges in the graph, then m = n^2 - m should be the condition. Please let me know about this!
https://gateoverflow.in/83854/gate1990-1-viii The above is the link of the question. In the solution it was assumed that the graph is complete. But in the question nothing is mentioned. Also a complete graph doesn't contain self loops. So what I'm thinking is, if we consider the ... m is the number of the edges in the graph, then m = n^2 - m should be the condition. Please let me know about this!
asked Feb 6 in Graph Theory hadarsh 5 points 21 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)
answered Jan 24 in Graph Theory SarathBaswa 855 points 35 views
0 votes
1 answer 55 views
Made Easy Workbook
What will be the number of components?
What will be the number of components?
answered Jan 14 in Graph Theory zxy123 3.6k points 55 views
0 votes
1 answer 47 views
TestBook Test Series
Consider G(V, E) be a complete undirected graph with 6 edges having a distinct weight from 1, 3, 9, 27, 81, and 243. Which of the following will NOT be the weight of them minimum spanning tree of G? (*This question may have multiple correct answers) A)121 B)13 C)40 D)31
Consider G(V, E) be a complete undirected graph with 6 edges having a distinct weight from 1, 3, 9, 27, 81, and 243. Which of the following will NOT be the weight of them minimum spanning tree of G? (*This question may have multiple correct answers) A)121 B)13 C)40 D)31
answered Jan 1 in Graph Theory wander 301 points 47 views
0 votes
0 answers 28 views
Self doubt from graph coloring
A graph which not having even length cycle then 3 color are sufficient to color vertices of graph such that no two adjacent vertex having same color?
A graph which not having even length cycle then 3 color are sufficient to color vertices of graph such that no two adjacent vertex having same color?
asked Dec 27, 2020 in Graph Theory Vaishali Trivedi 5 points 28 views
0 votes
1 answer 50 views
#made-easy #chromatic-number
Which of the following options are not the chromatic polynomial of the following graph: a) b) c) d) can someone explains?
Which of the following options are not the chromatic polynomial of the following graph: a) b) c) d) can someone explains?
answered Dec 26, 2020 in Graph Theory Sahil91 683 points 50 views
0 votes
0 answers 16 views
Made easy workbook
Let G be a Graph with V(G)={i|1<=i<=4n} where V(G) is the set of vertices of G. such that two numbers x and y are adjacent iff (x+y) is a multiple of 4. Find the number of the connected component in graph G 2 4 N None of these From the above k components, assume that each component Ck has mk vertices, then what is the maximum value of mk in the graph n 2n 3n None of these
Let G be a Graph with V(G)={i|1<=i<=4n} where V(G) is the set of vertices of G. such that two numbers x and y are adjacent iff (x+y) is a multiple of 4. Find the number of the connected component in graph G 2 4 N None of these From the above k components, assume that each component Ck has mk vertices, then what is the maximum value of mk in the graph n 2n 3n None of these
asked Dec 8, 2020 in Graph Theory Gautam9596 5 points 16 views
1 vote
1 answer 119 views
National olympiad of informatics
Siruseri Traffic Lights Adapted from Traffic Lights, International Olympiad in Informatics, 1999 In Siruseri, there are junctions connected by roads. There is at most one road between any pair of junctions. There is no road connecting a junction to itself. The travel time for a road is the ... 3 to 2 to 4 takes time 8 + 0 (no wait) + 6 + 1 (wait till 15) + 10 = 25.
Siruseri Traffic Lights Adapted from Traffic Lights, International Olympiad in Informatics, 1999 In Siruseri, there are junctions connected by roads. There is at most one road between any pair of junctions. There is no road connecting a junction to itself. The travel time for a road is the same in both directions. ... . 1 to 3 to 2 to 4 takes time 8 + 0 (no wait) + 6 + 1 (wait till 15) + 10 = 25.
answered Oct 12, 2020 in Graph Theory mayureshpatle 861 points 119 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?
answered Sep 18, 2020 in Graph Theory Shaik Masthan 1.6k 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
answered Sep 16, 2020 in Graph Theory ijnuhb 747 points 48 views
0 votes
0 answers 20 views
Ace Academy Practise Book
The chromatic number of a star graph with n vertices (n≥ 2) is ________.
The chromatic number of a star graph with n vertices (n≥ 2) is ________.
asked Sep 11, 2020 in Graph Theory Vishal_kumar98 37 points 20 views
0 votes
1 answer 32 views
Previous year question
The maximum number of edges in a bipartite graph on 12 vertices is _________. Please tell any generalized solution for this problem, if exists.
The maximum number of edges in a bipartite graph on 12 vertices is _________. Please tell any generalized solution for this problem, if exists.
answered Sep 2, 2020 in Graph Theory Sherrinford03 73 points 32 views
0 votes
1 answer 53 views
ACE Academy test series Question
Number of cycles of length 4 that are possible in the complete bipartite graph K(4,6) is
Number of cycles of length 4 that are possible in the complete bipartite graph K(4,6) is
answered Sep 2, 2020 in Graph Theory Scion_of_fire 49 points 53 views
0 votes
1 answer 70 views
Previous question paper
Construct a graph G with the following properties: edge connectivity of G =4, Vertex connectivity of G=3, and degree of every vertex of G >=5.
Construct a graph G with the following properties: edge connectivity of G =4, Vertex connectivity of G=3, and degree of every vertex of G >=5.
answered Aug 31, 2020 in Graph Theory Nikhil_dhama 225 points 70 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
answered Aug 16, 2020 in Graph Theory jayeshasawa001 2.5k points 37 views
0 votes
1 answer 61 views
kenneth rosen(chapter 10 ,theorem 5) 7th edition
theorem: HALL’S MARRIAGE THEOREM-The bipartite graph G=(V,E) with bipartite (v1,v2) has a complete matching from v1 to v2 if and only if |N(A)$\geq$|A| for all subsets of A of V1. explain with example
theorem: HALL’S MARRIAGE THEOREM-The bipartite graph G=(V,E) with bipartite (v1,v2) has a complete matching from v1 to v2 if and only if |N(A)$\geq$|A| for all subsets of A of V1. explain with example
answered Aug 16, 2020 in Graph Theory Arkaprava 867 points 61 views
0 votes
1 answer 54 views
Kenneth Rosen-7th edition-Chapter 10/10.8
THE FOUR COLOR THEOREM: The chromatic number of a planar graph is no greater than four. Question #40 (10.8) : Show that every planar graph G can be colored using six or fewer colors. Question #41 (10.8) : Show that every planar graph G ... is already stated in the four color theorem that we don't require more than 4 colors in order to color a planar graph.
THE FOUR COLOR THEOREM: The chromatic number of a planar graph is no greater than four. Question #40 (10.8) : Show that every planar graph G can be colored using six or fewer colors. Question #41 (10.8) : Show that every planar graph G can be colored using five ... questions if it is already stated in the four color theorem that we don't require more than 4 colors in order to color a planar graph.
answered Aug 16, 2020 in Graph Theory Arkaprava 867 points 54 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.
answered Aug 16, 2020 in Graph Theory jayeshasawa001 2.5k points 86 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?
answered Aug 16, 2020 in Graph Theory Arkaprava 867 points 21 views
0 votes
3 answers 123 views
GATE 2020 graph theory
How many number of cut vertex in tree if n is the number total vertex in tree?
How many number of cut vertex in tree if n is the number total vertex in tree?
answered Aug 16, 2020 in Graph Theory Arkaprava 867 points 123 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!
answered Aug 16, 2020 in Graph Theory Akanksha Agrawal 309 points 82 views
0 votes
1 answer 32 views
Kenneth Rosen Edition 7 Exercise 10.2 Question 44
Suppose that $d_{1}, d_{2}, ..., d_{n}$ is a graphic sequence. Show that there is a simple graph with vertices $v_{1}, v_{2}, …, v_{n}$ such that deg($v_{i}$) = $d_{i}$ for i = 1,2, …, n and $v_{1}$ is adjacent to $v_{2}, …, v_{d1 + 1}$.
Suppose that $d_{1}, d_{2}, ..., d_{n}$ is a graphic sequence. Show that there is a simple graph with vertices $v_{1}, v_{2}, …, v_{n}$ such that deg($v_{i}$) = $d_{i}$ for i = 1,2, …, n and $v_{1}$ is adjacent to $v_{2}, …, v_{d1 + 1}$.
answered Aug 16, 2020 in Graph Theory Arkaprava 867 points 32 views
0 votes
2 answers 28 views
#Grpaph-Theory #self Doubt Degree of Self loop
what is Degree of Self loop in undirected graph? Is it 2 or 1? please give a proper source
what is Degree of Self loop in undirected graph? Is it 2 or 1? please give a proper source
answered Aug 16, 2020 in Graph Theory jayeshasawa001 2.5k points 28 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?
answered Aug 16, 2020 in Graph Theory Arkaprava 867 points 34 views
0 votes
2 answers 45 views
#DM #Self-Doubt in previous year GATE
How many m len cycles in complete graph of n vertices? Please explain.
How many m len cycles in complete graph of n vertices? Please explain.
answered Aug 16, 2020 in Graph Theory jayeshasawa001 2.5k points 45 views
0 votes
2 answers 21 views
#Grpah Theory. #Self-Doubt
What are number of independent sets in Complete graph?
What are number of independent sets in Complete graph?
answered Aug 15, 2020 in Graph Theory Arkaprava 867 points 21 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
answered Aug 15, 2020 in Graph Theory Arkaprava 867 points 136 views
0 votes
1 answer 34 views
Proof of Euler equation
Euler equation is - |V| +|R| = |E| + 2 Can someone please show me how to come to above conclusion?
Euler equation is - |V| +|R| = |E| + 2 Can someone please show me how to come to above conclusion?
answered Aug 15, 2020 in Graph Theory Arkaprava 867 points 34 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
answered Aug 15, 2020 in Graph Theory Arkaprava 867 points 27 views
0 votes
1 answer 40 views
Self doubt GRAPH THEORY
answered Aug 12, 2020 in Graph Theory Arkaprava 867 points 40 views
0 votes
1 answer 41 views
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?
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?
answered Aug 12, 2020 in Graph Theory Arkaprava 867 points 41 views
To see more, click for all the questions in this category.
Dark theme
Muffin by Hélio Chun
Thanks to Q2A
...