Recent questions and answers in Graph Theory - GATE Overflow

+48 votes

5 answers

1

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 (35 points) | 5.5k views

+72 votes

8 answers

2

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 (6.9k points) | 11.5k views

+46 votes

4 answers

3

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 (6.9k points) | 4.9k views

+1 vote

1 answer

4

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.2k points) | 79 views

+18 votes

4 answers

5

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 (515 points) | 5.7k views

+2 votes

2 answers

6

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) | 443 views

0 votes

1 answer

7

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

answered Dec 23, 2019 in Graph Theory by mesh90 (61 points) | 334 views

+40 votes

11 answers

8

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 Junior (987 points) | 5.1k views

+31 votes

4 answers

9

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 Dec 20, 2019 in Graph Theory by shivam001 Junior (987 points) | 5.8k views

+69 votes

8 answers

10

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 Junior (987 points) | 8.6k views

+40 votes

7 answers

11

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

answered Dec 19, 2019 in Graph Theory by JashanArora Loyal (6.9k points) | 5.5k views

+7 votes

4 answers

12

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

+1 vote

2 answers

13

UGCNET-June2014-II-23
Consider a complete bipartite graph $k_{m,n}$. For which values of $m$ and $n$ does this, complete graph have a Hamilton circuit $m = 3, n = 2$ $m = 2, n = 3$ $m = n > 2$ $m = n > 3$

answered Dec 12, 2019 in Graph Theory by JashanArora Loyal (6.9k points) | 1.5k views

+23 votes

3 answers

14

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 Dec 11, 2019 in Graph Theory by neeraj_bhatt (335 points) | 1k views

+9 votes

5 answers

15

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 Dec 6, 2019 in Graph Theory by V0id (77 points) | 4k views

+39 votes

9 answers

16

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

answered Dec 3, 2019 in Graph Theory by JashanArora Loyal (6.9k points) | 10.5k views

+8 votes

9 answers

17

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

answered Dec 1, 2019 in Graph Theory by JashanArora Loyal (6.9k points) | 4.1k views

0 votes

2 answers

18

self doubt
What is the general formula for number of simple graph having n unlabelled vertices ??

answered Nov 30, 2019 in Graph Theory by Muneendra1337 (11 points) | 80 views

+18 votes

9 answers

19

GATE2018-30
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 between ... then $\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

answered Nov 17, 2019 in Graph Theory by Shailendra_ Junior (629 points) | 6.4k views

+1 vote

1 answer

20

Difference between DAG and Multi-stage graph
I have trouble understanding the difference between DAG and Multi-stage graph. I know what each of them is But I think that a multi-stage graph is also a DAG. Are multi-stage graphs a special kind of DAG?

answered Nov 15, 2019 in Graph Theory by mohithjagalmohanan (43 points) | 91 views

+2 votes

2 answers

21

CMI2018-A-4
Let $G=(V, E)$ be an undirected simple graph, and $s$ be a designated vertex in $G.$ For each $v\in V,$ let $d(v)$ be the length of a shortest path between $s$ and $v.$ For an edge $(u,v)$ in $G,$ what can not be the value of $d(u)-d(v)?$ $2$ $-1$ $0$ $1$

answered Nov 12, 2019 in Graph Theory by SPodder (13 points) | 53 views

+1 vote

1 answer

22

CMI2016-A-9
ScamTel has won a state government contract to connect $17$ cities by high-speed fibre optic links. Each link will connect a pair of cities so that the entire network is connected-there is a path from each city to every other city. The contract requires the network to remain ... $34$ $32$ $17$ $16$

answered Nov 9, 2019 in Graph Theory by `JEET Boss (19.2k points) | 64 views

+27 votes

4 answers

23

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 Oct 22, 2019 in Graph Theory by shaktisingh Junior (537 points) | 2.8k views

+2 votes

3 answers

24

Made easy
What is the chromatic number of following graphs? 1) 2)

answered Oct 16, 2019 in Graph Theory by chirudeepnamini Active (4.5k points) | 198 views

+1 vote

1 answer

25

graph Theory
Consider an undirected graph G where self-loops are not allowed. The vertex set of G is {(i,j):1<=i<=12,1<=j<=12}. There is an edge between (a, b) and (c, d) if |a-c|<=1 and |b-d|<=1. The number of edges in this graph is __________.

answered Oct 1, 2019 in Graph Theory by Mac2 (11 points) | 134 views

+33 votes

3 answers

26

GATE2001-2.15
How many undirected graphs (not necessarily connected) can be constructed out of a given set $V=\{v_1, v_2, \dots v_n\}$ of $n$ vertices? $\frac{n(n-1)} {2}$ $2^n$ $n!$ $2^\frac{n(n-1)} {2} $

answered Sep 26, 2019 in Graph Theory by HeartBleed Active (1k points) | 4.4k views

+1 vote

1 answer

27

CMI2018-B-3
Let $G$ be a simple graph on $n$ vertices. Prove that if $G$ has more than $\binom{n-1}{2}$ edges then $G$ is connected. For every $n>2$, find a graph $G_{n}$ which has exactly $n$ vertices and $\binom{n-1}{2}$ edges, and is not connected.

answered Sep 18, 2019 in Graph Theory by prashant jha 1 Loyal (5.9k points) | 43 views

+3 votes

2 answers

28

UGCNET-June-2019-II-5
For which values of $m$ and $n$ does the complete bipartite graph $k_{m,n}$ have a Hamiltonian circuit ? $m\neq n,\ \ m,n \geq 2$ $m\neq n,\ \ m,n \geq 3$ $m=n,\ \ m,n \geq 2$ $m= n,\ \ m,n \geq 3$

answered Sep 17, 2019 in Graph Theory by Raghava45 (349 points) | 302 views

0 votes

1 answer

29

CMI2019-B-4
Consider the assertion: Any connected undirected graph $G$ with at least two vertices contains a vertex $v$ such that deleting $v$ from $G$ results in a connected graph. Either give a proof of the assertion, or give a counterexample (thereby disproving the assertion).

answered Sep 17, 2019 in Graph Theory by `JEET Boss (19.2k points) | 40 views

0 votes

1 answer

30

CMI2018-A-9
Your college has sent a contingent to take part in a cultural festival at a neighbouring institution. Several team events are part of the programme. Each event takes place through the day with many elimination rounds. Your contingent is multi-talented ... : Find a maximum length simple cycle Find a maximum size independent set Find a maximum matching Find a maximal connected component

answered Sep 14, 2019 in Graph Theory by `JEET Boss (19.2k points) | 32 views

+14 votes

3 answers

31

ISI Entrance Exam MTech (CS)
Consider all possible trees with $n$ nodes. Let $k$ be the number of nodes with degree greater than $1$ in a given tree. What is the maximum possible value of $k$?

answered Sep 14, 2019 in Graph Theory by rohith1001 Active (2.1k points) | 992 views

+1 vote

1 answer

32

CMI2019-A-7
An interschool basketball tournament is being held at the Olympic sports complex. There are multiple basketball courts. Matches are scheduled in parallel, with staggered timings, to ensure that spectators always have some match or other available to watch. Each match ... solve? Find a minimal colouring. Find a minimal spanning tree. Find a minimal cut. Find a minimal vertex cover.

answered Sep 14, 2019 in Graph Theory by `JEET Boss (19.2k points) | 68 views

+1 vote

0 answers

33

CMI2018-B-5
Let $G=(V,E)$ be an undirected graph and $V=\{1,2,\cdots,n\}.$ The input graph is given to you by a $0-1$ matrix $A$ of size $n\times n$ as follows. For any $1\leq i,j\leq n,$ the entry $A[i,j]=1$ if and only if ... any two vertices are connected to each other by paths. Give a simple algorithm to find the number of connected components in $G.$ Analyze the time taken by your procedure.

asked Sep 13, 2019 in Graph Theory by gatecse Boss (17.5k points) | 26 views

+5 votes

2 answers

34

MadeEasy Test Series 2018: Graph Theory - Graph Coloring
answer given is 4. Please provide a detailed solution.

answered Sep 3, 2019 in Graph Theory by Rishav_Bhatt (283 points) | 181 views

0 votes

1 answer

35

answered Sep 1, 2019 in Graph Theory by Devvrat Tyagi (159 points) | 83 views

+28 votes

6 answers

36

GATE2014-2-51
A cycle on $n$ vertices is isomorphic to its complement. The value of $n$ is _____.

answered Aug 21, 2019 in Graph Theory by King Suleiman Active (1.2k points) | 4.3k views

+2 votes

2 answers

37

Graph Connectivity
Consider the given statements S1: In a simple graph G with 6 vertices, if degree of each vertex is 2, then Euler circuit exists in G. S2:In a simple graph G, if degree of each vertex is 3 then the graph G is connected. Which of the following is/are true?

answered Aug 5, 2019 in Graph Theory by IamDRD (109 points) | 255 views

+1 vote

2 answers

38

#ACE_ACADEMY_DISCRETE_MATHS_BOOKLET.
Which of the following is not true? (a) Number of edge-disjoint Hamiltonian cycles in $K_7$ is $3$ (b) If $G$ is a simple graph with $6$ vertices and the degree of each vertex is at least $3$, then the Hamiltonian cycle exists in ... simple graph with $5$ vertices and $7$ edges, then the Hamiltonian cycle exists in $G$ Please help me understand all the options.

answered Aug 1, 2019 in Graph Theory by Raghava45 (349 points) | 148 views

+2 votes

3 answers

39

UGCNET-June2015-II-5
Consider a Hamiltonian Graph(G) with no loops and parallel edges. Which of the following is true with respect to this graph (G)? deg (v) $\geq$ n/2 for each vertex of G $\mid E(G) \mid \geq $1/2 (n-1)(n-2)+2 edges deg(v) + deg(w) $\geq$ n fr every v and $\omega$ not connected by an edge a and b b and c a and c a, b, and c

answered Aug 1, 2019 in Graph Theory by tripu (11 points) | 2k views

+3 votes

1 answer

40

UGCNET-June-2019-II-4
Suppose that a connected planar graph has six vertices, each of degree four. Into how many regions is the plane divided by a planar representation of this graph? $6$ $8$ $12$ $20$

asked Jul 2, 2019 in Graph Theory by Arjun Veteran (431k points) | 294 views

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

Recent questions and answers in Graph Theory

50,737 questions

57,385 answers

198,548 comments

105,361 users