Recent questions and answers in Graph Theory - GATE Overflow

+15 votes

9 answers

1

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 19 hours ago in Graph Theory by Shailendra_ (449 points) | 5.4k views

+4 votes

3 answers

2

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 1 day ago in Graph Theory by manikantsharma (411 points) | 2.9k views

+1 vote

1 answer

3

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 2 days ago in Graph Theory by mohithjagalmohanan (15 points) | 72 views

+2 votes

2 answers

4

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 6 days ago in Graph Theory by SPodder (11 points) | 19 views

+1 vote

1 answer

5

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 in Graph Theory by `JEET Boss (11.3k points) | 52 views

+26 votes

4 answers

6

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 in Graph Theory by shaktisingh (303 points) | 2.5k views

+33 votes

8 answers

7

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

answered Oct 19 in Graph Theory by Saurabh666 (411 points) | 9.5k views

+2 votes

3 answers

8

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

answered Oct 16 in Graph Theory by chirudeepnamini Active (2.5k points) | 175 views

+1 vote

1 answer

9

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 in Graph Theory by Mac2 (11 points) | 122 views

+31 votes

3 answers

10

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 in Graph Theory by HeartBleed Junior (767 points) | 4k views

+35 votes

9 answers

11

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 Sep 24 in Graph Theory by HeartBleed Junior (767 points) | 4.5k views

+1 vote

1 answer

12

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 in Graph Theory by prashant jha 1 Loyal (5.7k points) | 20 views

+3 votes

2 answers

13

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 in Graph Theory by Raghava45 (349 points) | 220 views

0 votes

1 answer

14

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 in Graph Theory by `JEET Boss (11.3k points) | 15 views

0 votes

1 answer

15

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 in Graph Theory by `JEET Boss (11.3k points) | 15 views

+13 votes

3 answers

16

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 in Graph Theory by rohith1001 Junior (871 points) | 944 views

+1 vote

0 answers

17

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 in Graph Theory by gatecse Boss (16.6k points) | 14 views

+5 votes

2 answers

18

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

answered Sep 3 in Graph Theory by Rishav_Bhatt (145 points) | 164 views

0 votes

1 answer

19

answered Sep 1 in Graph Theory by Devvrat Tyagi (159 points) | 68 views

+27 votes

6 answers

20

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

answered Aug 21 in Graph Theory by King Suleiman Junior (917 points) | 3.8k views

+1 vote

2 answers

21

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 in Graph Theory by IamDRD (51 points) | 226 views

+1 vote

2 answers

22

#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 in Graph Theory by Raghava45 (349 points) | 111 views

+2 votes

3 answers

23

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 in Graph Theory by tripu (11 points) | 1.9k views

+1 vote

1 answer

24

UGCNET-June-2019-II-69
Consider the following properties with respect to a flow network $G=(V,E)$ in which a flow is a real-valued function $f:V \times V \rightarrow R$: $P_1$: For all $u, v, \in V, \: f(u,v)=-f(v,u)$ $P_2$: $\underset{v \in V}{\Sigma} f(u,v)=0$ for all $u \in V$ Which one of the following is/are correct? Only $P_1$ Only $P_2$ Both $P_1$ and $P_2$ Neither $P_1$ nor $P_2$

answered Jul 29 in Graph Theory by abhinav kumar (75 points) | 94 views

+2 votes

3 answers

25

ACE ACADEMY BOOKLET QUESTION
Let $G$ $=$ $(V, E)$ be a simple non-empty connected undirected graph, in which every vertex has degree 4. For any partition $V$ into two non-empty and non-overlapping subsets $S$ and $T$. Which of the following is true? There are at least two edges that ... $S$ and one end point in $T$ There are exactly one edge that have one end point in $S$ and one end point in $T$

answered Jul 26 in Graph Theory by gvjha3 (11 points) | 124 views

+1 vote

1 answer

26

graph theory(basic doubt)
Q.1)How many nonisomorphic simple graph are there with 6 vertices and 4 edges??

answered Jul 24 in Graph Theory by gorya506 (201 points) | 62 views

+37 votes

7 answers

27

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

answered Jul 14 in Graph Theory by PRANAV M (257 points) | 3.7k views

+41 votes

3 answers

28

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 Jul 5 in Graph Theory by pritishc (437 points) | 4.3k views

0 votes

1 answer

29

planar graph
Is this a planar graph ?

answered Jul 4 in Graph Theory by Peyush (11 points) | 99 views

+3 votes

1 answer

30

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$

answered Jul 3 in Graph Theory by Satbir Boss (20.7k points) | 227 views

+2 votes

1 answer

31

Graph Coloring
How many ways are there to color this graph from any $4$ of the following colors : Violet, Indigo, Blue, Green, Yellow, Orange and Red ? There is a condition that adjacent vertices should not be of the same color I am getting $1680$. Is it correct?

answered Jun 21 in Graph Theory by Satbir Boss (20.7k points) | 309 views

0 votes

1 answer

32

Planar Graph
Can minimum degree of a planar graph be $5$? Give some example

answered Jun 21 in Graph Theory by Satbir Boss (20.7k points) | 259 views

+1 vote

1 answer

33

Doubt
How many distinct unlabeled graphs are there with 4 vertices and 3 edges?

answered Jun 13 in Graph Theory by Gyanu Active (1.9k points) | 75 views

0 votes

1 answer

34

Zeal Test Series 2019: Graph Theory - Graph Connectivity

answered Jun 12 in Graph Theory by Gyanu Active (1.9k points) | 112 views

+2 votes

3 answers

35

Degree of vertices
Consider an undirected graph with $n$ vertices, vertex $1$ has degree $1$,while each vertex $2,3,.............,n-1$ has degree $4$.The degree of vertex $n$ is unknown. Which of the following statement must be true? Vertex $n$ has degree $1$ Graph is connected There is a path from vertex $1$ to vertex $n$ Spanning tree will include edge connecting vertex $1$ and vertex $n$

answered Jun 12 in Graph Theory by Sainath Mandavilli (23 points) | 133 views

0 votes

2 answers

36

ACE Workbook:
ACE Workbook: Q) Let G be a simple graph(connected) with minimum number of edges. If G has n vertices with degree-1,2 vertices of degree 2, 4 vertices of degree 3 and 3 vertices of degree-4, then value of n is ? Can anyone give the answer and how to approach these problems. Thanks in advance.

answered Jun 12 in Graph Theory by Akanksha Agrawal (129 points) | 94 views

+1 vote

1 answer

37

TIFR2019-B-12
Let $G=(V,E)$ be a directed graph with $n(\geq 2)$ vertices, including a special vertex $r$. Each edge $e \in E$ has a strictly positive edge weight $w(e)$. An arborescence in $G$ rooted at $r$ is a subgraph $H$ of $G$ in which every ... $w^*$ is less than the weight of the minimum weight directed Hamiltonian cycle in $G$, when $G$ has a directed Hamiltonian cycle

answered Jun 8 in Graph Theory by Arjun Veteran (423k points) | 314 views

+2 votes

1 answer

38

GATE1987-9d
Specify an adjacency-lists representation of the undirected graph given above.

answered Jun 5 in Graph Theory by Satbir Boss (20.7k points) | 346 views

0 votes

2 answers

39

#GRAPH THEORY
A simple regular graph n vertices and 24 edges, find all possible values of n.

answered Jun 4 in Graph Theory by rballiwal Active (1.2k points) | 107 views

0 votes

1 answer

40

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

answered Jun 4 in Graph Theory by rballiwal Active (1.2k points) | 56 views

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

Recent questions and answers in Graph Theory

50,650 questions

56,185 answers

193,937 comments

94,684 users