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

0 votes
1 answer 19 views
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
$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
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
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
0 votes
1 answer 70 views
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
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
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
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
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 r4? How you find it?
answered Aug 16, 2020 in Graph Theory Arkaprava 867 points 21 views
0 votes
3 answers 123 views
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
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
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
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
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
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
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
0 votes
1 answer 34 views
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
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
0 votes
1 answer 41 views
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.
...