Recent questions and answers in Graph Theory - GATE CSE Doubts

+1 vote

0 answers

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

asked Mar 9 in Graph Theory by donniedarko (39 points) | 16 views

0 votes

1 answer

Dominating set and Independent set.
Please explain the basic difference between Independent set and Dominating Set?

answered Feb 24 in Graph Theory by Dheera (-14 points) | 16 views

0 votes

0 answers

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!

asked Feb 6 in Graph Theory by hadarsh (5 points) | 15 views

+1 vote

1 answer

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)

answered Jan 24 in Graph Theory by SarathBaswa (849 points) | 24 views

0 votes

1 answer

Made Easy Workbook
What will be the number of components?

answered Jan 14 in Graph Theory by zxy123 (3.6k points) | 46 views

0 votes

1 answer

What is total number of planer graph can be formed with 6 vertices ?

answered Jan 12 in Graph Theory by zxy123 (3.6k points) | 38 views

0 votes

1 answer

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

answered Jan 1 in Graph Theory by wander (301 points) | 43 views

0 votes

0 answers

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?

asked Dec 27, 2020 in Graph Theory by Vaishali Trivedi (5 points) | 24 views

0 votes

1 answer

#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?

answered Dec 26, 2020 in Graph Theory by Sahil91 (683 points) | 32 views

0 votes

0 answers

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

asked Dec 8, 2020 in Graph Theory by Gautam9596 (5 points) | 10 views

+1 vote

1 answer

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.

answered Oct 12, 2020 in Graph Theory by mayureshpatle (861 points) | 91 views

+1 vote

1 answer

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?

answered Sep 18, 2020 in Graph Theory by Shaik Masthan (1.5k points) | 54 views

0 votes

1 answer

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

answered Sep 16, 2020 in Graph Theory by ijnuhb (747 points) | 36 views

0 votes

0 answers

Ace Academy Practise Book
The chromatic number of a star graph with n vertices (n≥ 2) is ________.

asked Sep 11, 2020 in Graph Theory by Vishal_kumar98 (37 points) | 16 views

0 votes

1 answer

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.

answered Sep 2, 2020 in Graph Theory by Sherrinford03 (73 points) | 24 views

0 votes

1 answer

ACE Academy test series Question
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 by Scion_of_fire (49 points) | 41 views

0 votes

1 answer

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.

answered Aug 31, 2020 in Graph Theory by Nikhil_dhama (151 points) | 46 views

0 votes

1 answer

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

answered Aug 16, 2020 in Graph Theory by jayeshasawa001 (2.5k points) | 26 views

0 votes

1 answer

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

answered Aug 16, 2020 in Graph Theory by Arkaprava (801 points) | 45 views

0 votes

1 answer

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.

answered Aug 16, 2020 in Graph Theory by Arkaprava (801 points) | 36 views

0 votes

1 answer

Graph Theory with Applications to Engineering and Computer Science, Narsingh Deo, Chapter 4 Question 27

answered Aug 16, 2020 in Graph Theory by jayeshasawa001 (2.5k points) | 60 views

0 votes

2 answers

Are planar graphs and vertex and edge cover included in GATE 2021 syllabus?

answered Aug 16, 2020 in Graph Theory by Arkaprava (801 points) | 25 views

0 votes

1 answer

What is the degree of region?
What is the degree of region r4? How you find it?

answered Aug 16, 2020 in Graph Theory by Arkaprava (801 points) | 14 views

0 votes

3 answers

GATE 2020 graph theory
How many number of cut vertex in tree if n is the number total vertex in tree?

answered Aug 16, 2020 in Graph Theory by Arkaprava (801 points) | 112 views

0 votes

4 answers

#DM #Graphs labeled simple graphs
How to count number of labeled simple graphs? Please explain!

answered Aug 16, 2020 in Graph Theory by Akanksha Agrawal (309 points) | 75 views

0 votes

1 answer

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}$.

answered Aug 16, 2020 in Graph Theory by Arkaprava (801 points) | 26 views

0 votes

2 answers

#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

answered Aug 16, 2020 in Graph Theory by jayeshasawa001 (2.5k points) | 25 views

0 votes

1 answer

Number of perfect matching in Kn?
Find number of perfect matching in Kn where n is even? Please explain too?

answered Aug 16, 2020 in Graph Theory by Arkaprava (801 points) | 23 views

0 votes

2 answers

#DM #Self-Doubt in previous year GATE
How many m len cycles in complete graph of n vertices? Please explain.

answered Aug 16, 2020 in Graph Theory by jayeshasawa001 (2.5k points) | 42 views

0 votes

2 answers

#Grpah Theory. #Self-Doubt
What are number of independent sets in Complete graph?

answered Aug 15, 2020 in Graph Theory by Arkaprava (801 points) | 18 views

0 votes

1 answer

Find no of Hamiltonian cycles in kn,n
How many Hamiltonian cycles are there in complete bipartite graph K n,n

answered Aug 15, 2020 in Graph Theory by Arkaprava (801 points) | 43 views

0 votes

1 answer

Proof of Euler equation
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 by Arkaprava (801 points) | 27 views

0 votes

1 answer

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

answered Aug 15, 2020 in Graph Theory by Arkaprava (801 points) | 21 views

0 votes

1 answer

Self doubt GRAPH THEORY

answered Aug 12, 2020 in Graph Theory by Arkaprava (801 points) | 32 views

0 votes

1 answer

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?

answered Aug 12, 2020 in Graph Theory by Arkaprava (801 points) | 27 views

0 votes

1 answer

Self doubt on graph theory
If we delete vertices from a graph, then what will happen to number of components ? will they increase or will remain same. Please answer my doubt.

answered Aug 11, 2020 in Graph Theory by Arkaprava (801 points) | 24 views

0 votes

1 answer

Why Euler circuit does not exist when number of odd degree vertices is 2

answered Aug 10, 2020 in Graph Theory by Arkaprava (801 points) | 37 views

0 votes

1 answer

I think the answer made easy gave is incorrect
How can G1 and G2 be isomorphic as in G2 we have a node of degree 2 and in G1 there is no node of degree 2 .

answered Aug 10, 2020 in Graph Theory by jayeshasawa001 (2.5k points) | 40 views

0 votes

0 answers

Textbook questions #doubt
What should be the answer?

asked Jul 22, 2020 in Graph Theory by premu (163 points) | 20 views

0 votes

0 answers

adjacency matrix in graphs
A represents an adjacency matrix of Graph G The number of paths of length 8 from vertex 1 to vertex 4??

asked May 8, 2020 in Graph Theory by Abhipsa (17 points) | 24 views

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

Recent questions and answers in Graph Theory

9,197 questions

3,182 answers

14,686 comments

96,162 users