Recent questions and answers in Graph Theory - GATE Overflow

0 votes

2 answers

1

UGCNET-Dec2006-II: 3
The number of edges in a complete graph with N vertices is equal to: $N (N−1)$ $2N−1$ $N−1$ $N(N−1)/2$

answered 19 hours ago in Graph Theory by immanujs Active (3.8k points) | 18 views

0 votes

1 answer

2

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$

answered 1 day ago in Graph Theory by smsubham Boss (16.5k points) | 10 views

0 votes

0 answers

3

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$

asked 2 days ago in Graph Theory by Lakshman Patel RJIT Veteran (61.3k points) | 9 views

0 votes

1 answer

4

UGCNET-Dec2007-II: 2
The number of edges in a complete graph with ‘n’ vertices is equal to : $n(n-1)$ $\large\frac{n(n-1)}{2}$ $n^2$ $2n-1$

answered 4 days ago in Graph Theory by chirudeepnamini Loyal (5.3k points) | 21 views

0 votes

1 answer

5

UGCNET-Dec2004-II: 4
The following lists are the degrees of all the vertices of a graph : $1,2,3,4,5$ $3,4,5,6,7$ $1, 4, 5, 8, 6$ $3,4,5,6$ (i) and (ii) (iii) and (iv) (iii) and (ii) (ii) and (iv)

answered 6 days ago in Graph Theory by Divya Devi (23 points) | 17 views

0 votes

0 answers

6

UGCNET-Dec2004-II: 23
Weighted graph : Is a bi-directional graph. Is directed graph. Is graph in which number associated with arc. Eliminates table method.

asked Mar 26 in Graph Theory by jothee Veteran (107k points) | 5 views

0 votes

2 answers

7

NIELIT July 2017_75
Choose the most appropriate definition of plane graph A) A simple graph which is isomorphic to Hamiltonian graph B) A graph drawn in a plane such away that if the vertex set of graph can be partitioned into two non - empty disjoint subset X and Y in such a way ... A graph drawn in a plane in such a way that any pair of edges meet only at their end vertices D) None of the option

answered Mar 19 in Graph Theory by topper98 Junior (589 points) | 340 views

+3 votes

5 answers

8

NIELIT July 2017_73
For the graph shown, which of the following paths is a Hamilton circuit ? A) ABCDCFDEFAEA B) AEDCBAF C) AEFDCBA D) AFCDEBA

answered Mar 19 in Graph Theory by topper98 Junior (589 points) | 628 views

0 votes

2 answers

9

NIELIT July 2017_72
The following graph has no Euler circuit because A) It has 7 vertices B) It is even-valent (all vertices have even valence) C) It is not connected D) It does not have an Euler circuit

answered Mar 19 in Graph Theory by topper98 Junior (589 points) | 361 views

0 votes

2 answers

10

NIELIT July 2017_71
Consider the following graph L and find the bridges, if any A) No bridge B) {d, e} C) {c, d} D) {c, d} and {c, f}

answered Mar 19 in Graph Theory by topper98 Junior (589 points) | 395 views

+13 votes

6 answers

11

GATE2019-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

answered Mar 17 in Graph Theory by immanujs Active (3.8k points) | 4.7k views

0 votes

3 answers

12

NIELIT Scientist-B Dec 2017_56
Let G be a simple undirected graph on $n=3x$ vertices ($x>=1$) with chromatic number 3, then maximum number of edges in G is : (A) $n(n-1)/2$ (B) $n^{n-2}$ (C) $nx$ (D) $n$

answered Mar 8 in Graph Theory by vivekgatecs2020 (137 points) | 460 views

+28 votes

3 answers

13

GATE2002-1.4
The minimum number of colours required to colour the vertices of a cycle with $n$ nodes in such a way that no two adjacent nodes have the same colour is $2$ $3$ $4$ $n-2 \left \lfloor \frac{n}{2} \right \rfloor+2$

answered Mar 7 in Graph Theory by vivekgatecs2020 (137 points) | 3.1k views

+33 votes

4 answers

14

GATE2009-3
Which one of the following is TRUE for any simple connected undirected graph with more than $2$ vertices? No two vertices have the same degree. At least two vertices have the same degree. At least three vertices have the same degree. All vertices have the same degree.

answered Mar 7 in Graph Theory by vivekgatecs2020 (137 points) | 2.7k views

+2 votes

2 answers

15

Zeal Test Series 2019: Graph Theory - Graph Coloring
what is index ?

answered Mar 2 in Graph Theory by Parth Narodia (23 points) | 167 views

+2 votes

3 answers

16

GATE2020-CS-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 _______

answered Feb 27 in Graph Theory by immanujs Active (3.8k points) | 1.2k views

+10 votes

3 answers

17

GATE2005-10
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$

answered Feb 21 in Graph Theory by Pratyush Priyam Kuan Active (1.1k points) | 1.4k views

+31 votes

5 answers

18

GATE2002-1.25, ISRO2008-30, ISRO2016-6
The maximum number of edges in a n-node undirected graph without self loops is $n^2$ $\frac{n(n-1)}{2}$ $n-1$ $\frac{(n+1)(n)}{2}$

answered Feb 20 in Graph Theory by Pratyush Priyam Kuan Active (1.1k points) | 6k views

+24 votes

7 answers

19

GATE2006-IT-11
If all the edge weights of an undirected graph are positive, then any subset of edges that connects all the vertices and has minimum total weight is a Hamiltonian cycle grid hypercube tree

answered Feb 20 in Graph Theory by Pratyush Priyam Kuan Active (1.1k points) | 2.1k views

+29 votes

5 answers

20

GATE2006-73
The $2^n$ vertices of a graph $G$ corresponds to all subsets of a set of size $n$, for $n \geq 6$. Two vertices of $G$ are adjacent if and only if the corresponding sets intersect in exactly two elements. The number of connected components in $G$ is: $n$ $n + 2$ $2^{\frac{n}{2}}$ $\frac{2^{n}}{n}$

answered Feb 20 in Graph Theory by Pratyush Priyam Kuan Active (1.1k points) | 3k views

+24 votes

2 answers

21

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

answered Feb 20 in Graph Theory by Pratyush Priyam Kuan Active (1.1k points) | 3k views

+18 votes

5 answers

22

GATE2004-IT-5
What is the maximum number of edges in an acyclic undirected graph with $n$ vertices? $n-1$ $n$ $n+1$ $2n-1$

answered Feb 20 in Graph Theory by Pratyush Priyam Kuan Active (1.1k points) | 2.1k views

+12 votes

3 answers

23

GATE1994-2.5
The number of edges in a regular graph of degree $d$ and $n$ vertices is ____________

answered Feb 20 in Graph Theory by Pratyush Priyam Kuan Active (1.1k points) | 5.3k views

+23 votes

4 answers

24

TIFR2018-A-9
How many ways are there to assign colours from range $\left\{1,2,\ldots,r\right\}$ to vertices of the following graph so that adjacent vertices receive distinct colours? $r^{4}$ $r^{4} - 4r^{3}$ $r^{4}-5r^{3}+8r^{2}-4r$ $r^{4}-4r^{3}+9r^{2}-3r$ $r^{4}-5r^{3}+10r^{2}-15r$

answered Feb 20 in Graph Theory by Pratyush Priyam Kuan Active (1.1k points) | 1.1k views

+31 votes

4 answers

25

TIFR2017-B-1
A vertex colouring with three colours of a graph $G=(V, E)$ is a mapping $c: V \rightarrow \{R, G, B\}$ so that adjacent vertices receive distinct colours. Consider the following undirected graph. How many vertex colouring with three colours does this graph have? $3^9$ $6^3$ $3 \times 2^8$ $27$ $24$

answered Feb 20 in Graph Theory by Pratyush Priyam Kuan Active (1.1k points) | 1.1k views

+25 votes

3 answers

26

GATE2008-IT-3
What is the chromatic number of the following graph? $2$ $3$ $4$ $5$

answered Feb 20 in Graph Theory by Pratyush Priyam Kuan Active (1.1k points) | 2.3k views

+25 votes

6 answers

27

GATE2004-77
The minimum number of colours required to colour the following graph, such that no two adjacent vertices are assigned the same color, is $2$ $3$ $4$ $5$

answered Feb 19 in Graph Theory by Pratyush Priyam Kuan Active (1.1k points) | 2.9k views

0 votes

3 answers

28

TIFR2020-B-11
Which of the following graphs are bipartite? Only $(1)$ Only $(2)$ Only $(2)$ and $(3)$ None of $(1),(2),(3)$ All of $(1),(2),(3)$

answered Feb 11 in Graph Theory by nitin_kumar (273 points) | 91 views

+43 votes

8 answers

29

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

answered Feb 1 in Graph Theory by rohit9 (143 points) | 5.9k views

0 votes

1 answer

30

Virtual Gate Test Series: Discrete Mathematics - Graph Theory
Let $G$ be a graph on $n$ vertices with $4n-16$ edges.Consider the following: 1. There is a vertex of degree smaller than $8$ in $G.$ 2. There is a vertex such that there are less than $16$ vertices at a distance exactly $2$ from it. Which of the following is TRUE: 1 only 2 only Both 1 and 2 Neither 1 nor 2

answered Jan 29 in Graph Theory by Pankajmjx (33 points) | 168 views

+51 votes

5 answers

31

GATE2007-IT-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$

answered Jan 6 in Graph Theory by endurance1 (45 points) | 5.7k views

+75 votes

8 answers

32

GATE2012-38
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$

answered Jan 3 in Graph Theory by JashanArora Loyal (8.3k points) | 12.2k views

+48 votes

4 answers

33

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

answered Jan 3 in Graph Theory by JashanArora Loyal (8.3k points) | 5.1k views

+1 vote

1 answer

34

NTA NET DEC2019( shortest distance)
Consider a weighted directed graph. The current shortest distance from sources S to node x is represented by d[v] = 29 . d[u] = 15 , w[u,v] = 12. What is the updated value of d[v]based on current information? 1) 29 2) 27 3) 25 4) 17

answered Dec 26, 2019 in Graph Theory by `JEET Boss (19.7k points) | 166 views

+18 votes

4 answers

35

GATE2015-1-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_______________.

answered Dec 24, 2019 in Graph Theory by scholaraniket Junior (547 points) | 6k views

+3 votes

2 answers

36

Euler Path
Which of the following Graph has Euler Path but is not an Euler Graph? A. K1,1 B.K2,10 C.K2,11 D.K10,11.

answered Dec 24, 2019 in Graph Theory by Nirmal Gaur Active (2.3k points) | 476 views

0 votes

1 answer

37

no of simple graph possible with 6 vertices and 4 edges is ?

answered Dec 23, 2019 in Graph Theory by mesh90 (69 points) | 384 views

+42 votes

11 answers

38

GATE2014-3-51
If $G$ is the forest with $n$ vertices and $k$ connected components, how many edges does $G$ have? $\left\lfloor\frac {n}{k}\right\rfloor$ $\left\lceil \frac{n}{k} \right\rceil$ $n-k$ $n-k+1$

answered Dec 20, 2019 in Graph Theory by shivam001 Active (1.2k points) | 5.4k views

+71 votes

8 answers

39

GATE2014-1-51
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______.

answered Dec 20, 2019 in Graph Theory by shivam001 Active (1.2k points) | 9.1k views

+7 votes

4 answers

40

ISRO2011-35
How many edges are there in a forest with $v$ vertices and $k$ components? $(v+1) - k$ $(v+1)/2 - k$ $v - k$ $v + k$

answered Dec 17, 2019 in Graph Theory by Debjit0007 (55 points) | 2.4k views

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

Recent questions and answers in Graph Theory

51,925 questions

58,730 answers

200,106 comments

111,799 users