Recent questions and answers in Graph Theory

10 votes

6 answers

1

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)$

Nihal Singh answered in Graph Theory Oct 8

1.8k views

2 votes

5 answers

2

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

kalam_11 answered in Graph Theory Oct 6

2k views

7 votes

3 answers

3

GATE CSE 1988 | Question: 13iii
Are the two digraphs shown in the above figure isomorphic? Justify your answer.

Pkaryan123 answered in Graph Theory Sep 21

638 views

23 votes

7 answers

4

GATE CSE 2015 Set 1 | Question: 54
Let G be a connected planar graph with 10 vertices. If the number of edges on each face is three, then the number of edges in G is_______________.

Prarbdh Tiwari answered in Graph Theory Sep 20

by Prarbdh Tiwari

13.6k views

0 votes

1 answer

5

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

M_eight answered in Graph Theory Aug 28

227 views

22 votes

6 answers

6

GATE IT 2004 | Question: 5
What is the maximum number of edges in an acyclic undirected graph with $n$ vertices? $n-1$ $n$ $n+1$ $2n-1$

raja11sep answered in Graph Theory Aug 28

4.3k views

12 votes

4 answers

7

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 _______

sridhar15399 answered in Graph Theory Aug 7

by sridhar15399

5.6k views

45 votes

6 answers

8

GATE CSE 2013 | Question: 26
The line graph $L(G)$ of a simple graph $G$ is defined as follows: There is exactly one vertex $v(e)$ in $L(G)$ for each edge $e$ in $G$. For any two edges $e$ and $e'$ in $G$, $L(G)$ has an edge between $v(e)$ and $v(e')$, if and only if $e$ ... of a planar graph is planar. (S) The line graph of a tree is a tree. $P$ only $P$ and $R$ only $R$ only $P, Q$ and $S$ only

sridhar15399 answered in Graph Theory Aug 6

by sridhar15399

12.1k views

19 votes

6 answers

9

CMI2013-A-06
A simple graph is one in which there are no self-loops and each pair of distinct vertices is connected by at most one edge. Let $G$ be a simple graph on $8$ vertices such that there is a vertex of degree $1$, a vertex of degree $2$, a vertex of degree $3$, a vertex ... degree $6$ and a vertex of degree $7$. Which of the following can be the degree of the last vertex? $3$ $0$ $5$ $4$

varunrajarathnam answered in Graph Theory Jul 25

by varunrajarathnam

3.8k views

32 votes

6 answers

10

GATE CSE 2008 | Question: 23
Which of the following statements is true for every planar graph on $n$ vertices? The graph is connected The graph is Eulerian The graph has a vertex-cover of size at most $\frac{3n}{4}$ The graph has an independent set of size at least $\frac{n}{3}$

HitechGa answered in Graph Theory Jul 7

8.2k views

23 votes

6 answers

11

GATE CSE 2019 | Question: 38
Let $G$ be any connected, weighted, undirected graph. $G$ has a unique minimum spanning tree, if no two edges of $G$ have the same weight. $G$ has a unique minimum spanning tree, if, for every cut of $G$, there is a unique minimum-weight edge crossing the cut. Which of the following statements is/are TRUE? I only II only Both I and II Neither I nor II

HitechGa answered in Graph Theory Jul 7

11.9k views

9 votes

4 answers

12

GATE CSE 1988 | Question: 2xvi
Write the adjacency matrix representation of the graph given in below figure.

HitechGa answered in Graph Theory Jul 6

2.1k views

55 votes

11 answers

13

GATE CSE 1994 | Question: 1.6, ISRO2008-29
The number of distinct simple graphs with up to three nodes is $15$ $10$ $7$ $9$

ShouvikSVK answered in Graph Theory Jul 3

22.7k views

3 votes

3 answers

14

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.

rish1602 answered in Graph Theory Jul 2

267 views

61 votes

7 answers

15

GATE CSE 2004 | Question: 79
How many graphs on $n$ labeled vertices exist which have at least $\frac{(n^2 - 3n)}{ 2}$ edges ? $^{\left(\frac{n^2-n}{2}\right)}C_{\left(\frac{n^2-3n} {2}\right)}$ $^{{\large\sum\limits_{k=0}^{\left (\frac{n^2-3n}{2} \right )}}.\left(n^2-n\right)}C_k$ $^{\left(\frac{n^2-n}{2}\right)}C_n$ $^{{\large\sum\limits_{k=0}^n}.\left(\frac{n^2-n}{2}\right)}C_k$

rish1602 answered in Graph Theory Jun 27

8.9k views

6 votes

3 answers

16

Virtual Gate Test Series: Discrete Mathematics - Graph Theory (Matching Number)
Find the matching number for the given graph-

rish1602 answered in Graph Theory Jun 15

483 views

6 votes

2 answers

17

Articulation point in graph

rish1602 answered in Graph Theory Jun 15

977 views

7 votes

1 answer

18

Strongly connected component
Find the no of strongly connected components for the below graph. $5$ $4$ $9$ $2$

rish1602 answered in Graph Theory Jun 15

353 views

9 votes

2 answers

19

Discrete maths: Graph theory [Test series]
Consider $G$ be a directed graph whose vertex set is a set numbers from $2$ to $120$. There is an edge from vertex $b$ if $b=K\times a$. Where $K$ is any natural number. Then the number of connected components are _____________.

rish1602 answered in Graph Theory Jun 8

514 views

17 votes

3 answers

20

TIFR2012-B-2
In a graph, the degree of a vertex is the number of edges incident (connected) on it. Which of the following is true for every graph $G$? There are even number of vertices of even degree. There are odd number of vertices of even degree. There are even number of vertices of odd degree. There are odd number of vertices of odd degree. All the vertices are of even degree.

rish1602 answered in Graph Theory Jun 6

1.5k views

23 votes

10 answers

21

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

rish1602 answered in Graph Theory Jun 6

12.5k views

23 votes

4 answers

22

TIFR2013-B-1
Let $G= (V, E)$ be a simple undirected graph on $n$ vertices. A colouring of $G$ is an assignment of colours to each vertex such that endpoints of every edge are given different colours. Let $\chi (G)$ denote the chromatic number of $G$, i.e. the minimum numbers of colours ... $a\left(G\right)\leq \frac{n}{\chi \left(G\right)}$ None of the above

rish1602 answered in Graph Theory Jun 6

2.5k views

23 votes

4 answers

23

GATE CSE 2005 | Question: 35
How many distinct binary search trees can be created out of $4$ distinct keys? $5$ $14$ $24$ $42$

rish1602 answered in Graph Theory Jun 3

8.2k views

24 votes

5 answers

24

GATE CSE 2015 Set 2 | Question: 28
A graph is self-complementary if it is isomorphic to its complement. For all self-complementary graphs on $n$ vertices, $n$ is A multiple of 4 Even Odd Congruent to 0 $mod$ 4, or, 1 $mod$ 4.

rish1602 answered in Graph Theory Jun 3

5.6k views

24 votes

4 answers

25

CMI2011-A-07
Let $G=(V, E)$ be a graph. Define $\overline{G}$ to be $(V, \overline{E})$, where for all $u, \: v \: \in V \: , (u, v) \in \overline{E}$ if and only if $(u, v) \notin E$. Then which of the following is true? $\overline{G}$ is always ... $G$ is not connected. At least one of $G$ and $\overline{G}$ connected. $G$ is not connected or $\overline{G}$ is not connected

rish1602 answered in Graph Theory Jun 3

1.1k views

27 votes

4 answers

26

GATE CSE 1995 | Question: 1.25
The minimum number of edges in a connected cyclic graph on $n$ vertices is: $n-1$ $n$ $n+1$ None of the above

rish1602 answered in Graph Theory Jun 3

13k views

37 votes

6 answers

27

GATE IT 2008 | Question: 27
$G$ is a simple undirected graph. Some vertices of $G$ are of odd degree. Add a node $v$ to $G$ and make it adjacent to each odd degree vertex of $G$. The resultant graph is sure to be regular complete Hamiltonian Euler

rish1602 answered in Graph Theory Jun 1

8k views

51 votes

9 answers

28

GATE CSE 2003 | Question: 36
How many perfect matching are there in a complete graph of $6$ vertices? $15$ $24$ $30$ $60$

rish1602 answered in Graph Theory May 28

12.1k views

62 votes

6 answers

29

GATE IT 2007 | Question: 25
What is the largest integer $m$ such that every simple connected graph with $n$ vertices and $n$ edges contains at least $m$ different spanning trees ? $1$ $2$ $3$ $n$

rish1602 answered in Graph Theory May 28

10.9k views

56 votes

6 answers

30

GATE CSE 2007 | Question: 23
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

Deepakk Poonia (Dee) answered in Graph Theory May 15

by Deepakk Poonia (Dee)

15.3k views

1 vote

1 answer

31

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$

Hira Thakur answered in Graph Theory May 15

244 views

1 vote

1 answer

32

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$

Hira Thakur answered in Graph Theory May 14

1.4k views

0 votes

1 answer

33

Virtual Gate Test Series: Discrete Mathematics - Graph Theory
Which of the following is true? The size of the maximum independent set on G is the same as the size of maximum clique on G'(Complement of G) The size of minimum vertex cover on G is the same as the size of maximum clique on G'(complement of G) The size of minimum vertex cover on G is the same as the size of maximum clique on G'

Deepakk Poonia (Dee) answered in Graph Theory May 13

by Deepakk Poonia (Dee)

193 views

1 vote

2 answers

34

UGCNET-june2009-ii-12
The complete graph with four vertices has $k$ edges where $k$ is : $3$ $4$ $5$ $6$

Hira Thakur answered in Graph Theory May 12

4.7k views

28 votes

3 answers

35

TIFR2018-B-8
In an undirected graph $G$ with $n$ vertices, vertex $1$ has degree $1$, while each vertex $2,\ldots,n-1$ has degree $10$ and the degree of vertex $n$ is unknown, Which of the following statement must be TRUE on the graph $G$? There is a path from vertex $1$ to ... $n$ has degree $1$. The diameter of the graph is at most $\frac{n}{10}$ All of the above choices must be TRUE

rish1602 answered in Graph Theory May 12

3.2k views

29 votes

4 answers

36

GATE CSE 1989 | Question: 3-vi
Which of the following graphs is/are planner?

rish1602 answered in Graph Theory May 12

4.5k views

29 votes

4 answers

37

GATE CSE 2005 | Question: 11
Let $G$ be a simple graph with $20$ vertices and $100$ edges. The size of the minimum vertex cover of G is $8$. Then, the size of the maximum independent set of $G$ is: $12$ $8$ less than $8$ more than $12$

rish1602 answered in Graph Theory May 10

6.7k views

35 votes

6 answers

38

TIFR2010-B-36
In a directed graph, every vertex has exactly seven edges coming in. What can one always say about the number of edges going out of its vertices? Exactly seven edges leave every vertex. Exactly seven edges leave some vertex. Some vertex has at least seven edges leaving it. The number of edges coming out of vertex is odd. None of the above.

rish1602 answered in Graph Theory May 10

3.3k views

33 votes

4 answers

39

GATE CSE 1999 | Question: 1.15
The number of articulation points of the following graph is $0$ $1$ $2$ $3$

rish1602 answered in Graph Theory May 10

5.2k views

0 votes

1 answer

40

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

196 views

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

Follow @gateoverflow

GATE Overflow

Recent questions and answers in Graph Theory

Search GATE Overflow