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

5 votes

1 answer

31

GO Classes Test Series 2024 | Discrete Mathematics | Test 5 | Question: 6
Let $\text{G = (V, E)}$ be a finite directed acyclic graph with $|\text{E}| > 0.$ Which of the following is not necessarily true? $\text{G}$ has a vertex with no incoming edge. $\text{G}$ has a ... no outgoing edge. $\text{G}$ has an isolated vertex, that is, one with neither an incoming edge nor an outgoing edge. None

Let $\text{G = (V, E)}$ be a finite directed acyclic graph with $|\text{E}| 0.$ Which of the following is not necessarily true?$\text{G}$ has a vertex with no incoming e...

GO Classes

602 views

GO Classes asked May 11, 2022

3 votes

1 answer

32

GO Classes Test Series 2024 | Discrete Mathematics | Test 5 | Question: 7
A Hamiltonian circuit in a graph is a closed path that visits every vertex in the graph exactly once. A Hamiltonian circuit ends up at the vertex from where it started. If a graph has some Hamiltonian circuit, then the graph is called a ... following is/are a hamiltonian graph? $\text{G1}$ $\text{G2}$ $\text{G3}$ $\text{G4}$

A Hamiltonian circuit in a graph is a closed path that visits every vertex in the graph exactly once. A Hamiltonian circuit ends up at the vertex from where it started.If...

GO Classes

552 views

GO Classes asked May 11, 2022

4 votes

1 answer

33

GO Classes Test Series 2024 | Discrete Mathematics | Test 5 | Question: 8
Let $\text{G}$ be a simple graph where $\text{V(G)} = \{1, 2, \dots , 100\}$ and there is an edge between two distinct vertices $a$ and $b$ iff $a$ divides $b.$ Which of the following statements are true for $\text{G}?$ ... $\text{G}$ is $1.$ $\text{G}$ is connected. The diameter of $\text{G}$ is $6.$

Let $\text{G}$ be a simple graph where $\text{V(G)} = \{1, 2, \dots , 100\}$ and there is an edge between two distinct vertices $a$ and $b$ iff $a$ divides $b.$Which of t...

GO Classes

374 views

GO Classes asked May 11, 2022

4 votes

1 answer

34

GO Classes Test Series 2024 | Discrete Mathematics | Test 5 | Question: 11
Let $\text{K}(4,6)$ be the complete bipartite graph on $10$ vertices, having $4$ vertices in one part and having $6$ ... is a complete graph. Either $\text{K}(m,n)$ OR complement of $\text{K}(m,n)$ is dis-connected.

Let $\text{K}(4,6)$ be the complete bipartite graph on $10$ vertices, having $4$ vertices in one part and having $6$ vertices in another part. Which of the following is/a...

GO Classes

367 views

GO Classes asked May 11, 2022

3 votes

1 answer

35

GO Classes Test Series 2024 | Discrete Mathematics | Test 5 | Question: 23
The height of a rooted tree is the maximum height of any leaf. The length of the unique path from a leaf of the tree to the root is, by definition, the height of that leaf. A rooted tree in which each non-leaf vertex has at ... maximum height $h = L-1.$ It is possible to have a binary tree with $35$ leaves and height $100.$

The height of a rooted tree is the maximum height of any leaf. The length of the unique path from a leaf of the tree to the root is, by definition, the height of that lea...

GO Classes

630 views

GO Classes asked May 11, 2022

19 votes

5 answers

36

GATE CSE 2022 | Question: 20
Consider a simple undirected graph of $10$ vertices. If the graph is disconnected, then the maximum number of edges it can have is _______________ .

Consider a simple undirected graph of $10$ vertices. If the graph is disconnected, then the maximum number of edges it can have is _______________ .

Arjun

8.7k views

Arjun asked Feb 15, 2022

14 votes

3 answers

37

GATE CSE 2022 | Question: 27
Consider a simple undirected unweighted graph with at least three vertices. If $\textit{A}$ is the adjacency matrix of the graph, then the number of $3–$cycles in the graph is given by the trace of $\textit{A}^{3}$ $\textit{A}^{3}$ divided by $2$ $\textit{A}^{3}$ divided by $3$ $\textit{A}^{3}$ divided by $6$

Consider a simple undirected unweighted graph with at least three vertices. If $\textit{A}$ is the adjacency matrix of the graph, then the number of $3–$cycles in the g...

Arjun

7.5k views

Arjun asked Feb 15, 2022

16 votes

4 answers

38

GATE CSE 2022 | Question: 42
Which of the properties hold for the adjacency matrix $A$ of a simple undirected unweighted graph having $n$ vertices? The diagonal entries of $A^{2}$ ... . If there is at least a $1$ in each of $A\text{'s}$ rows and columns, then the graph must be connected.

Which of the properties hold for the adjacency matrix $A$ of a simple undirected unweighted graph having $n$ vertices?The diagonal entries of $A^{2}$ are the degrees of t...

Arjun

7.4k views

Arjun asked Feb 15, 2022

0 votes

2 answers

39

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

494 views

raja11sep asked Jan 5, 2022

3 votes

1 answer

40

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

577 views

soujanyareddy13 asked Mar 25, 2021

35 votes

6 answers

41

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

9.9k views

Arjun asked Feb 18, 2021

5 votes

1 answer

42

GATE Overflow Test Series | Mock GATE | Test 4 | Question: 22
In a graph, a vertex is called an articulation point if removing it and all the edges associated with it results in the increase of the number of connected components in the graph. Let $G$ be a graph contain $10$ vertices, if $G$ has $8$ articulation points then what must be the number of edges in graph $G$? $45$ $10$ $9$ $8$

In a graph, a vertex is called an articulation point if removing it and all the edges associated with it results in the increase of the number of connected components in ...

gatecse

359 views

gatecse asked Feb 1, 2021

7 votes

1 answer

43

GATE Overflow Test Series | Mock GATE | Test 3 | Question: 37
How many walks of length four are there from $a$ to $c$ in the simple graph $G$?

How many walks of length four are there from $a$ to $c$ in the simple graph $G$?

gatecse

783 views

gatecse asked Jan 26, 2021

2 votes

2 answers

44

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

1 answer

45

GATE Overflow Test Series | Mixed Subjects | Test 3 | Question: 29
Which of the following is/are possible for unlabelled trees/graphs? (Mark all the appropriate choices) Two different trees with the same number of vertices and the same number of edges. Two different simple graphs with $8$ vertices all of ... $5$ vertices all of degree $4.$ Two different graphs with $7$ vertices all of degree $3.$

Which of the following is/are possible for unlabelled trees/graphs? (Mark all the appropriate choices)Two different trees with the same number of vertices and the same nu...

gatecse

134 views

gatecse asked Oct 15, 2020

1 votes

1 answer

46

GATE Overflow Test Series | Discrete Mathematics | Test 4 | Question: 1
If $G$ is a simple graph with $16$ edges and $\overline{G}$ has $12$ edges, how many vertices does the complement graph $\overline{G}$ have?

If $G$ is a simple graph with $16$ edges and $\overline{G}$ has $12$ edges, how many vertices does the complement graph $\overline{G}$ have?

gatecse

195 views

gatecse asked Sep 14, 2020

4 votes

1 answer

47

GATE Overflow Test Series | Discrete Mathematics | Test 4 | Question: 3
The number of possible connected simple graphs with $3$ labelled vertices is ________

The number of possible connected simple graphs with $3$ labelled vertices is ________

gatecse

317 views

gatecse asked Sep 14, 2020

4 votes

2 answers

48

GATE Overflow Test Series | Discrete Mathematics | Test 4 | Question: 6
Which of the following is/are correct? $S_1:$ A connected graph of at least $2$ vertices has an Euler circuit if and only if degree of every vertex is even. $S_2:$ A connected graph has an Euler path if and only if there are at most two vertices with odd degree. $S_1$ only $S_2$ only Both $S_1$ and $S_2$ Neither $S_1$ nor $S_2$

Which of the following is/are correct?$S_1:$ A connected graph of at least $2$ vertices has an Euler circuit if and only if degree of every vertex is even.$S_2:$ A connec...

gatecse

323 views

gatecse asked Sep 14, 2020

1 votes

1 answer

49

GATE Overflow Test Series | Discrete Mathematics | Test 4 | Question: 7
Suppose a simple graph has $45$ edges, $5$ vertices of degree $6$, and all others of degree $5$. How many vertices does the graph have?

Suppose a simple graph has $45$ edges, $5$ vertices of degree $6$, and all others of degree $5$. How many vertices does the graph have?

gatecse

126 views

gatecse asked Sep 14, 2020

3 votes

1 answer

50

GATE Overflow Test Series | Discrete Mathematics | Test 4 | Question: 8
The maximum number of edges in a disconnected graph having $12$ vertices is _______

The maximum number of edges in a disconnected graph having $12$ vertices is _______

gatecse

154 views

gatecse asked Sep 14, 2020

2 votes

2 answers

51

GATE Overflow Test Series | Discrete Mathematics | Test 4 | Question: 10
The maximum number of edges a graph with $45$ vertices, and $15$ connected components is ________

The maximum number of edges a graph with $45$ vertices, and $15$ connected components is ________

gatecse

179 views

gatecse asked Sep 14, 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