Recent questions and answers in Graph Theory

Recent questions and answers in Graph Theory

1 vote

3 answers

1

Zeal Test Series 2019: Graph Theory - Graph Connectivity

AngshukN answered in Graph Theory 7 hours ago

462 views

0 votes

0 answers

2

Introduction to Graph Theory Exercises
This is the problem snapshot

AngshukN asked in Graph Theory 8 hours ago

12 views

2 votes

1 answer

3

CMI2015-A-04a
A college prepares its timetable by grouping courses in slots A, B, C, . . . All courses in a slot meet at the same time, and courses in different slots have disjoint timings. Course registration has been completed and the administration now knows ... a spanning tree with minimum number of edges Find a minimal coloring Find a minimum size vertex cover Find a maximum size independent

s_dr_13 answered in Graph Theory 5 days ago

414 views

1 vote

3 answers

4

No of spanning Trees
Let $K_n$ denote the complete undirected graph with $n$ vertices where n is an even number. Find the maximum number of spanning trees of $K_n$ that can be formed in such a way that no two of these spanning trees have a common edge.

samarpita answered in Graph Theory May 13

2.9k views

0 votes

1 answer

5

What is the number of faces in a connected plane graph having 23 vertices, 30 edges?

Aditya_ answered in Graph Theory Apr 27

44 views

1 vote

3 answers

6

GATE CSE 2022 | Question: 42
Which of the properties hold for the adjacency matrix $A$ of a simple undirected unweighted graph having $n$ vertices? The diagonal entries of $A^{2}$ ... . If there is at least a $1$ in each of $A\text{'s}$ rows and columns, then the graph must be connected.

felics moses 1 answered in Graph Theory Apr 22

by felics moses 1

1.1k views

35 votes

8 answers

7

GATE CSE 2014 Set 2 | Question: 3
The maximum number of edges in a bipartite graph on $12$ vertices is____

nij padariya answered in Graph Theory Apr 5

by nij padariya

23.5k views

2 votes

4 answers

8

GATE CSE 2022 | Question: 20
Consider a simple undirected graph of $10$ vertices. If the graph is disconnected, then the maximum number of edges it can have is _______________ .

s_dr_13 answered in Graph Theory Mar 12

930 views

2 votes

1 answer

9

GATE CSE 2022 | Question: 40
The following simple undirected graph is referred to as the Peterson graph. Which of the following statements is/are $\text{TRUE}?$ The chromatic number of the graph is $3.$ The graph has a Hamiltonian path. The following graph is isomorphic to the Peterson ... $3.$ (A subset of vertices of a graph form an independent set if no two vertices of the subset are adjacent.)

Shaik Masthan answered in Graph Theory Feb 15

by Shaik Masthan

797 views

2 votes

2 answers

10

GATE CSE 2022 | Question: 27
Consider a simple undirected unweighted graph with at least three vertices. If $\textit{A}$ is the adjacency matrix of the graph, then the number of $3–$cycles in the graph is given by the trace of $\textit{A}^{3}$ $\textit{A}^{3}$ divided by $2$ $\textit{A}^{3}$ divided by $3$ $\textit{A}^{3}$ divided by $6$

Deepak Poonia answered in Graph Theory Feb 15

by Deepak Poonia

772 views

16 votes

5 answers

11

GATE CSE 2020 | Question: 52
Graph $G$ is obtained by adding vertex $s$ to $K_{3,4}$ and making $s$ adjacent to every vertex of $K_{3,4}$. The minimum number of colours required to edge-colour $G$ is _______

Nitesh_Yadav answered in Graph Theory Feb 9

by Nitesh_Yadav

7.4k views

57 votes

8 answers

12

GATE CSE 2003 | Question: 40
A graph $G=(V,E)$ satisfies $\mid E \mid \leq 3 \mid V \mid - 6$. The min-degree of $G$ is defined as $\min_{v\in V}\left\{ \text{degree }(v)\right \}$. Therefore, min-degree of $G$ cannot be $3$ $4$ $5$ $6$

thewolf answered in Graph Theory Jan 31

10.9k views

39 votes

9 answers

13

GATE CSE 2017 Set 2 | Question: 23
$G$ is an undirected graph with $n$ vertices and $25$ edges such that each vertex of $G$ has degree at least $3$. Then the maximum possible value of $n$ is _________ .

Kabir5454 answered in Graph Theory Jan 26

12.5k views

1 vote

0 answers

14

Made Easy Full length Test
Options Given were---- ADC ABC Both the above None of these According to me the answer should be {A,B,C,D} as this is the largest set and every node is capable to reach every other node.. but the answer given was option C so can anyone plz tell me whats the correct answer?

Sagar475 asked in Graph Theory Jan 18

128 views

2 votes

1 answer

15

max weighted MST possible
Let G be a complete undirected graph on 5 vertices 10 edges, with weights being 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. Let X be the value of the maximum possible weight a MST of G can have. Then the value of x will be_____ the answer to this question is given as 11 but there is no procedure given . Please ,can anyone help me out in understanding the procedure

supreetshukla answered in Graph Theory Jan 15

by supreetshukla

371 views

0 votes

2 answers

16

self doubt
Both euler path and euler circuit can be present in a graph ?

yuyutsu answered in Graph Theory Jan 7

137 views

25 votes

11 answers

17

GATE CSE 2019 | Question: 12
Let $G$ be an undirected complete graph on $n$ vertices, where $n > 2$. Then, the number of different Hamiltonian cycles in $G$ is equal to $n!$ $(n-1)!$ $1$ $\frac{(n-1)!}{2}$

HM answered in Graph Theory Dec 30, 2021

by HM

14.9k views

1 vote

1 answer

18

Testbook Test Series

rsansiya111 asked in Graph Theory Dec 18, 2021

115 views

6 votes

5 answers

19

GATE CSE 2021 Set 1 | Question: 16
In an undirected connected planar graph $G$, there are eight vertices and five faces. The number of edges in $G$ is _________.

Arjun asked in Graph Theory Feb 18, 2021

by Arjun

4.4k views

18 votes

6 answers

20

GATE CSE 2021 Set 1 | Question: 36
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$ ... $\text{diam}(G_2) = \text{diam}(G)$ $\text{diam}(G)< \text{diam}(G_2)\leq 2\; \text{diam}(G)$

Arjun asked in Graph Theory Feb 18, 2021

by Arjun

4.1k views

3 votes

3 answers

21

JEST2020
Let G(V,E) be a simple graph. Let G’(V,E’) be a graph obtained from G such that (u,v) is an edge in G’ if (u,v) is not an edge in G. Which of the following is true? At least one of G or G’ are connected. G is necessarily disconnected. Both G and G’ are disconnected. None of the above.

vivek_mishra asked in Graph Theory Feb 15, 2021

by vivek_mishra

370 views

1 vote

1 answer

22

NIELIT 2016 MAR Scientist C - Section B: 20
Degree of each vertex in $K_n$ is $n$ $n-1$ $n-2$ $2n-1$

Lakshman Patel RJIT asked in Graph Theory Apr 2, 2020

by Lakshman Patel RJIT

289 views

0 votes

1 answer

23

NIELIT 2017 OCT Scientific Assistant A (CS) - Section B: 7
The number of the edges in a regular graph of degree $’d’$ and $’n’$ vertices is Maximum of $n,d$ $n+d$ $nd$ $nd/2$

Lakshman Patel RJIT asked in Graph Theory Apr 1, 2020

by Lakshman Patel RJIT

329 views

3 votes

3 answers

24

NIELIT 2017 DEC Scientific Assistant A - Section B: 20
Total number of simple graphs that can be drawn using six vertices are: $2^{15}$ $2^{14}$ $2^{13}$ $2^{12}$

Lakshman Patel RJIT asked in Graph Theory Mar 31, 2020

by Lakshman Patel RJIT

1.1k views

1 vote

1 answer

25

NIELIT 2017 DEC Scientific Assistant A - Section B: 38
If a planner graph, having $25$ vertices divides the plane into $17$ different regions. Then how many edges are used to connect the vertices in this graph. $20$ $30$ $40$ $50$

Lakshman Patel RJIT asked in Graph Theory Mar 31, 2020

by Lakshman Patel RJIT

1.2k views

0 votes

2 answers

26

NIELIT 2016 MAR Scientist B - Section B: 1
The number of ways to cut a six sided convex polygon whose vertices are labeled into four triangles using diagonal lines that do not cross is $13$ $14$ $12$ $11$

Lakshman Patel RJIT asked in Graph Theory Mar 31, 2020

by Lakshman Patel RJIT

1.2k views

0 votes

1 answer

27

NIELIT 2016 MAR Scientist B - Section B: 3
Maximum degree of any node in a simple graph with $n$ vertices is $n-1$ $n$ $n/2$ $n-2$

Lakshman Patel RJIT asked in Graph Theory Mar 31, 2020

by Lakshman Patel RJIT

419 views

1 vote

1 answer

28

NIELIT 2016 DEC Scientist B (CS) - Section B: 5
Let $G$ be a simple undirected planar graph on $10$ vertices with $15$ edges. If $G$ is a connected graph, then the number of bounded faces in any embedding of $G$ on the plane is equal to: $3$ $4$ $5$ $6$

Lakshman Patel RJIT asked in Graph Theory Mar 31, 2020

by Lakshman Patel RJIT

699 views

0 votes

1 answer

29

NIELIT 2017 July Scientist B (IT) - Section B: 1
Given an undirected graph $G$ with $V$ vertices and $E$ edges, the sum of the degrees of all vertices is $E$ $2E$ $V$ $2V$

Lakshman Patel RJIT asked in Graph Theory Mar 30, 2020

by Lakshman Patel RJIT

7.8k views

0 votes

2 answers

30

NIELIT 2017 July Scientist B (IT) - Section B: 2
Which of the following is an advantage of adjacency list representation over adjacency matrix representation of a graph? In adjacency list representation, space is saved for sparse graphs. Deleting a vertex in adjacency list ... Adding a vertex in adjacency list representation is easier than adjacency matrix representation. All of the option.

Lakshman Patel RJIT asked in Graph Theory Mar 30, 2020

by Lakshman Patel RJIT

11.1k views

0 votes

1 answer

31

NIELIT 2017 July Scientist B (IT) - Section B: 3
A path in graph $G$, which contains every vertex of $G$ and only once? Euler circuit Hamiltonian path Euler Path Hamiltonian Circuit

Lakshman Patel RJIT asked in Graph Theory Mar 30, 2020

by Lakshman Patel RJIT

1.2k views

0 votes

1 answer

32

NIELIT 2017 July Scientist B (IT) - Section B: 5
In a given following graph among the following sequences: abeghf abfehg abfhge afghbe Which are depth first traversals of the above graph? I,II and IV only I and IV only II,III and IV only I,III and IV only

Lakshman Patel RJIT asked in Graph Theory Mar 30, 2020

by Lakshman Patel RJIT

477 views

1 vote

1 answer

33

NIELIT 2017 July Scientist B (IT) - Section B: 6
Considering the following graph, which one of the following set of edges represents all the bridges of the given graph? $(a,b), (e,f)$ $(a,b), (a,c)$ $(c,d), (d,h)$ $(a,b)$

Lakshman Patel RJIT asked in Graph Theory Mar 30, 2020

by Lakshman Patel RJIT

504 views

0 votes

1 answer

34

NIELIT 2017 July Scientist B (IT) - Section B: 7
Which of the following statements is/are TRUE? $S1$:The existence of an Euler circuit implies that an Euler path exists. $S2$:The existence of an Euler path implies that an Euler circuit exists. $S1$ is true. $S2$ is true. $S1$ and $S2$ both are true. $S1$ and $S2$ both are false.

Lakshman Patel RJIT asked in Graph Theory Mar 30, 2020

by Lakshman Patel RJIT

1.0k views

1 vote

1 answer

35

NIELIT 2017 July Scientist B (IT) - Section B: 8
A connected planar graph divides the plane into a number of regions. If the graph has eight vertices and these are linked by $13$ edges, then the number of regions is: $5$ $6$ $7$ $8$

Lakshman Patel RJIT asked in Graph Theory Mar 30, 2020

by Lakshman Patel RJIT

2.0k views

1 vote

1 answer

36

NIELIT 2017 July Scientist B (IT) - Section B: 12
Let $G$ be a simple connected planar graph with $13$ vertices and $19$ edges. Then, the number of faces in the planar embedding of the graph is $6$ $8$ $9$ $13$

Lakshman Patel RJIT asked in Graph Theory Mar 30, 2020

by Lakshman Patel RJIT

392 views

0 votes

1 answer

37

NIELIT 2017 July Scientist B (IT) - Section B: 15
The number of diagonals that can be drawn by joining the vertices of an octagon is $28$ $48$ $20$ None of the option

Lakshman Patel RJIT asked in Graph Theory Mar 30, 2020

by Lakshman Patel RJIT

300 views

0 votes

0 answers

38

NIELIT 2017 July Scientist B (CS) - Section B: 2
Which of the following statements is/are TRUE for an undirected graph? Number of odd degree vertices is even Sum of degrees of all vertices is even P only Q only Both P and Q Neither P nor Q

Lakshman Patel RJIT asked in Graph Theory Mar 30, 2020

by Lakshman Patel RJIT

854 views

0 votes

4 answers

39

NIELIT 2017 July Scientist B (CS) - Section B: 11
Consider the following graph $L$ and find the bridges,if any. No bridge $\{d,e\}$ $\{c,d\}$ $\{c,d\}$ and $\{c,f\}$

Lakshman Patel RJIT asked in Graph Theory Mar 30, 2020

by Lakshman Patel RJIT

761 views

Help get things started by asking a question.

Follow @gateoverflow

Recent questions and answers in Graph Theory

Search GATE Overflow for GATE CSE