Recent questions tagged graph-theory

2 votes

3 answers

1

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

by Arjun

1.7k views

9 votes

5 answers

2

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

by Arjun

1.5k views

0 votes

1 answer

3

NIELIT Scientific Assistant A 2020 November: 96
In an undirected graph, if we add the degrees of all vertices, it is: odd even cannot be determined always $n+1,$ where $n$ is number of nodes

gatecse asked in Unknown Category Dec 9, 2020

55 views

0 votes

1 answer

4

UGCNET-Oct2020-II: 26
Let $G$ be a directed graph whose vertex set is the set of numbers from $1$ to $100$. There is an edge from a vertex $i$ to a vertex $j$ if and only if either $j=i+1$ or $j=3i$. The minimum number of edges in a path in $G$ from vertex $1$ to vertex $100$ is ______ $23$ $99$ $4$ $7$

jothee asked in Discrete Mathematics Nov 20, 2020

by jothee

295 views

0 votes

1 answer

5

UGCNET-Oct2020-II: 53
Consider the following statements: Any tree is $2$-colorable A graph $G$ has no cycles of even length if it is bipartite A graph $G$ is $2$-colorable if is bipartite A graph $G$ can be colored with $d+1$ colors if $d$ is the maximum degree of any vertex in the graph ... $(b)$ and $(c)$ are incorrect $(b)$ and $(e)$ are incorrect $(a)$ and $(d)$ are incorrect

jothee asked in Discrete Mathematics Nov 20, 2020

by jothee

459 views

0 votes

0 answers

6

UGCNET-Oct2020-II: 86
Let $G$ be a simple undirected graph, $T_D$ be a DFS tree on $G$, and $T_B$ be the BFS tree on $G$. Consider the following statements. Statement $I$: No edge of $G$ is a cross with respect to $T_D$ Statement $II$ ... $I$ and Statement $II$ are false Statement $I$ is correct but Statement $II$ is false Statement $I$ is incorrect but Statement $II$ is true

jothee asked in Discrete Mathematics Nov 20, 2020

by jothee

174 views

0 votes

1 answer

7

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

184 views

0 votes

1 answer

8

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

222 views

3 votes

3 answers

9

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

793 views

1 vote

1 answer

10

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

713 views

0 votes

2 answers

11

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

967 views

0 votes

1 answer

12

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

257 views

1 vote

1 answer

13

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

433 views

0 votes

1 answer

14

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

5k views

0 votes

2 answers

15

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

6.1k views

0 votes

1 answer

16

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

803 views

0 votes

1 answer

17

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

338 views

0 votes

1 answer

18

NIELIT 2017 July Scientist B (IT) - Section B: 6
Considering the following graph, which one of the following set of edged 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

282 views

0 votes

1 answer

19

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

493 views

1 vote

1 answer

20

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

1.3k views

1 vote

1 answer

21

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

220 views

0 votes

1 answer

22

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

211 views

0 votes

0 answers

23

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

628 views

0 votes

4 answers

24

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

550 views

0 votes

3 answers

25

NIELIT 2017 July Scientist B (CS) - Section B: 12
The following graph has no Euler circuit because It has $7$ vertices. It is even-valent (all vertices have even valence). It is not connected. It does not have a Euler circuit.

Lakshman Patel RJIT asked in Graph Theory Mar 30, 2020

by Lakshman Patel RJIT

963 views

0 votes

7 answers

26

NIELIT 2017 July Scientist B (CS) - Section B: 13
For the graph shown, which of the following paths is a Hamilton circuit? $ABCDCFDEFAEA$ $AEDCBAF$ $AEFDCBA$ $AFCDEBA$

Lakshman Patel RJIT asked in Graph Theory Mar 30, 2020

by Lakshman Patel RJIT

975 views

Page:

1
2
3
4
5
6
...
23
next »

Follow @gateoverflow

GATE Overflow

Recent questions tagged graph-theory

Search GATE Overflow