Recent questions tagged graph-theory / GATE Overflow for GATE CSE

0 votes

2 answers

151

Self Doubt
Why is the vertex connectivity of a graph always less than or equal to its edge connectivity?

Why is the vertex connectivity of a graph always less than or equal to its edge connectivity?

raja11sep

499 views

raja11sep asked Jan 5, 2022

1 votes

1 answer

152

TIFR GS 2022 Computer Science Question

Shailin Shah

651 views

Shailin Shah asked Dec 23, 2021

2 votes

1 answer

153

graph theory
complete directed graph with 8 vertices has 28 edges this statement is true or false plese explain?

complete directed graph with 8 vertices has 28 edges this statement is true or falseplese explain?

jugnu1337

547 views

jugnu1337 asked Dec 17, 2021

0 votes

1 answer

154

Nptel Assignment Question
Consider the following strategy to convert a graph with negative edge weights to one that does not have negative edge weights. Let the maximum magnitude negative edge weight in the graph be -k. Then, for each edge in the graph with weight w, ... all graphs. The claim is true for connected acyclic graphs. The claim is not true in general for connected graphs with cycles

Consider the following strategy to convert a graph with negative edge weights to one that does not have negative edge weights. Let the maximum magnitude negative edge wei...

rsansiya111

1.2k views

rsansiya111 asked Dec 8, 2021

0 votes

0 answers

155

Show that the chromatic polynomial of a graph consisting of a single circuit of length n is Pn=λ-1n+λ-1-1n.

This question is related to graph theory colour covering

EthicEtheR

393 views

EthicEtheR asked Nov 20, 2021

1 votes

1 answer

156

TIFR CSE 2021 | Part A | Question: 6
A matching in a graph is a set of edges such that no two edges in the set share a common vertex. Let $G$ be a graph on $n$ $\textit{vertices}$ in which there is a subset $M$ of $m$ $\textit{edges}$ which is a matching. Consider a random process where each vertex in the ... $\left ( 1-p^{2} \right )^{m}$ $1-\left ( 1-p\left ( 1-p \right ) \right )^{m}$

A matching in a graph is a set of edges such that no two edges in the set share a common vertex. Let $G$ be a graph on $n$ $\textit{vertices}$ in which there is a subset ...

soujanyareddy13

771 views

soujanyareddy13 asked Mar 25, 2021

2 votes

0 answers

157

TIFR CSE 2021 | Part A | Question: 15
Let $P$ be a convex polygon with sides $5, 4, 4, 3$. For example, the following: Consider the shape in the plane that consists of all points within distance $1$ from some point in $P$. If $\ell$ is the perimeter of the shape, which of the following ... the given information. $20\leq \ell < 21$ $21\leq \ell< 22$ $22\leq \ell< 23$ $23\leq \ell< 24$

Let $P$ be a convex polygon with sides $5, 4, 4, 3$. For example, the following:Consider the shape in the plane that consists of all points within distance $1$ from some ...

soujanyareddy13

472 views

soujanyareddy13 asked Mar 25, 2021

3 votes

1 answer

158

TIFR CSE 2021 | Part B | Question: 12
Let $G$ be an undirected graph. For any two vertices $u, v$ in $G$, let $\textrm{cut} (u, v)$ be the minimum number of edges that should be deleted from $G$ so that there is no path between $u$ and $v$ in the resulting graph. Let $a, b, c, d$ be $4$ ... $\textrm{cut} (b,d) = 2$, $\textrm{cut} (b,c) = 2$ and $\textrm{cut} (c,d) = 1$

Let $G$ be an undirected graph. For any two vertices $u, v$ in $G$, let $\textrm{cut} (u, v)$ be the minimum number of edges that should be deleted from $G$ so that there...

soujanyareddy13

586 views

soujanyareddy13 asked Mar 25, 2021

2 votes

1 answer

159

TIFR CSE 2021 | Part B | Question: 13
Let $A$ be a $3 \times 6$ matrix with real-valued entries. Matrix $A$ has rank $3$. We construct a graph with $6$ vertices where each vertex represents distinct column in $A$, and there is an edge between two vertices if the two columns represented ... is connected. There is a clique of size $3$. The graph has a cycle of length $4$. The graph is $3$-colourable.

Let $A$ be a $3 \times 6$ matrix with real-valued entries. Matrix $A$ has rank $3$. We construct a graph with $6$ vertices where each vertex represents distinct column in...

soujanyareddy13

609 views

soujanyareddy13 asked Mar 25, 2021

3 votes

2 answers

160

TIFR CSE 2021 | Part B | Question: 14
Consider the following greedy algorithm for colouring an $n$-vertex undirected graph $G$ with colours $c_{1}, c_{2}, \dots:$ consider the vertices of $G$ ... $m\left ( n, r \right ) = nr$ $m\left ( n, r \right ) = n\binom{r}{2}$

Consider the following greedy algorithm for colouring an $n$-vertex undirected graph $G$ with colours $c_{1}, c_{2}, \dots:$ consider the vertices of $G$ in any sequence ...

soujanyareddy13

744 views

soujanyareddy13 asked Mar 25, 2021

13 votes

5 answers

161

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

In an undirected connected planar graph $G$, there are eight vertices and five faces. The number of edges in $G$ is _________.

Arjun

8.2k views

Arjun asked Feb 18, 2021

35 votes

6 answers

162

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

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

Arjun

10.0k views

Arjun asked Feb 18, 2021

1 votes

1 answer

163

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

In an undirected graph, if we add the degrees of all vertices, it is:oddevencannot be determinedalways $n+1,$ where $n$ is number of nodes

gatecse

419 views

gatecse asked Dec 9, 2020

2 votes

2 answers

164

NIELIT Scientific Assistant A 2020 November: 19
What is the total number of ways to reach from $A$ to $B$ in the network given? $12$ $16$ $20$ $22$

What is the total number of ways to reach from $A$ to $B$ in the network given?$12$$16$$20$$22$

gatecse

1.0k views

gatecse asked Dec 8, 2020

1 votes

2 answers

165

UGC NET CSE | October 2020 | Part 2 | Question: 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$

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

go_editor

955 views

go_editor asked Nov 20, 2020

0 votes

1 answer

166

UGC NET CSE | October 2020 | Part 2 | Question: 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 ... incorrect $(ii)$ and $(iii)$ are incorrect $(ii)$ and $(v)$ are incorrect $(i)$ and $(iv)$ are incorrect

Consider the following statements:Any tree is $2$-colorableA graph $G$ has no cycles of even length if it is bipartiteA graph $G$ is $2$-colorable if is bipartiteA graph ...

go_editor

1.6k views

go_editor asked Nov 20, 2020

0 votes

0 answers

167

UGC NET CSE | October 2020 | Part 2 | Question: 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$: ... Statement $II$ are false Statement $I$ is correct but Statement $II$ is false Statement $I$ is incorrect but Statement $II$ is true

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

go_editor

628 views

go_editor asked Nov 20, 2020

1 votes

1 answer

168

NIELIT 2016 MAR Scientist C - Section B: 20
Degree of each vertex in $K_n$ is $n$ $n-1$ $n-2$ $2n-1$

Degree of each vertex in $K_n$ is $n$$n-1$$n-2$$2n-1$

admin

520 views

admin asked Apr 2, 2020

0 votes

1 answer

169

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$

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$

admin

572 views

admin asked Apr 1, 2020

3 votes

3 answers

170

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

Total number of simple graphs that can be drawn using six vertices are:$2^{15}$$2^{14}$$2^{13}$$2^{12}$

admin

2.3k views

admin asked Mar 31, 2020

1 votes

1 answer

171

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$

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

admin

2.2k views

admin asked Mar 31, 2020

0 votes

2 answers

172

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$

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$

admin

2.1k views

admin asked Mar 31, 2020

0 votes

1 answer

173

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$

Maximum degree of any node in a simple graph with $n$ vertices is$n-1$$n$$n/2$$n-2$

admin

663 views

admin asked Mar 31, 2020

1 votes

1 answer

174

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$

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

admin

1.3k views

admin asked Mar 31, 2020

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true