Recent questions and answers in Graph Theory - GATE CSE Doubts

+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 in Graph Theory by mayureshpatle (855 points) | 63 views

0 votes

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 in Graph Theory by Shaik Masthan (1.4k points) | 35 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 in Graph Theory by Shashank Rustagi (513 points) | 28 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 in Graph Theory by Vishal_kumar98 (7 points) | 13 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 in Graph Theory by Sherrinford03 (73 points) | 19 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 in Graph Theory by Scion_of_fire (47 points) | 24 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 in Graph Theory by Nikhil_dhama (151 points) | 33 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 in Graph Theory by jayeshasawa001 (2.5k points) | 25 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 in Graph Theory by Arkaprava (711 points) | 30 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 in Graph Theory by Arkaprava (711 points) | 30 views

0 votes

1 answer

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

answered Aug 16 in Graph Theory by jayeshasawa001 (2.5k points) | 34 views

0 votes

2 answers

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

answered Aug 16 in Graph Theory by Arkaprava (711 points) | 21 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 in Graph Theory by Arkaprava (711 points) | 11 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 in Graph Theory by Arkaprava (711 points) | 87 views

0 votes

4 answers

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

answered Aug 16 in Graph Theory by Akanksha Agrawal (309 points) | 59 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 in Graph Theory by Arkaprava (711 points) | 23 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 in Graph Theory by jayeshasawa001 (2.5k points) | 17 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 in Graph Theory by Arkaprava (711 points) | 17 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 in Graph Theory by jayeshasawa001 (2.5k points) | 29 views

0 votes

2 answers

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

answered Aug 15 in Graph Theory by Arkaprava (711 points) | 12 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 in Graph Theory by Arkaprava (711 points) | 12 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 in Graph Theory by Arkaprava (711 points) | 23 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 in Graph Theory by Arkaprava (711 points) | 14 views

0 votes

1 answer

Self doubt GRAPH THEORY

answered Aug 12 in Graph Theory by Arkaprava (711 points) | 29 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 in Graph Theory by Arkaprava (711 points) | 20 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 in Graph Theory by Arkaprava (711 points) | 21 views

0 votes

1 answer

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

answered Aug 10 in Graph Theory by Arkaprava (711 points) | 32 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 in Graph Theory by jayeshasawa001 (2.5k points) | 31 views

0 votes

0 answers

Textbook questions #doubt
What should be the answer?

asked Jul 22 in Graph Theory by premu (97 points) | 17 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 in Graph Theory by Abhipsa (5 points) | 20 views

0 votes

0 answers

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?

asked May 7 in Graph Theory by Abhipsa (5 points) | 26 views

0 votes

0 answers

Graph theory 3-Ordered trees possible for a given no of nodes

asked Apr 28 in Graph Theory by ramcharantej_24 (13 points) | 19 views

0 votes

0 answers

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$

asked Apr 18 in Graph Theory by admin (193 points) | 12 views

0 votes

0 answers

GATE1994-1.6, ISRO2008-29 Video Solution
The number of distinct simple graphs with up to three nodes is $15$ $10$ $7$ $9$

asked Apr 18 in Graph Theory by admin (193 points) | 3 views

0 votes

0 answers

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______.

asked Apr 18 in Graph Theory by admin (193 points) | 7 views

0 votes

0 answers

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

asked Apr 18 in Graph Theory by admin (193 points) | 5 views

0 votes

0 answers

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

asked Apr 18 in Graph Theory by admin (193 points) | 6 views

0 votes

0 answers

GATE2002-1.25, ISRO2008-30, ISRO2016-6 Video Solution

asked Apr 18 in Graph Theory by admin (193 points) | 11 views

0 votes

0 answers

GATE2003-36 Video Solution
How many perfect matching are there in a complete graph of $6$ vertices? $15$ $24$ $30$ $60$

asked Apr 18 in Graph Theory by admin (193 points) | 3 views

0 votes

0 answers

GATE2016-2-03 Video Solution
The minimum number of colours that is sufficient to vertex-colour any planar graph is ________.

asked Apr 18 in Graph Theory by admin (193 points) | 4 views

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

Recent questions and answers in Graph Theory

8,430 questions

2,707 answers

13,232 comments

95,452 users