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

4 votes

1 answer

121

GO Classes Test Series 2024 | Discrete Mathematics | Test 5 | Question: 4
The number of simple undirected graphs with $6$ labeled vertices and exactly $3$ edges is _________

The number of simple undirected graphs with $6$ labeled vertices and exactly $3$ edges is _________

GO Classes

553 views

GO Classes asked May 11, 2022

5 votes

1 answer

122

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

618 views

GO Classes asked May 11, 2022

3 votes

1 answer

123

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

567 views

GO Classes asked May 11, 2022

4 votes

1 answer

124

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

376 views

GO Classes asked May 11, 2022

4 votes

1 answer

125

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

376 views

GO Classes asked May 11, 2022

2 votes

1 answer

126

GO Classes Test Series 2024 | Discrete Mathematics | Test 5 | Question: 13
For the following graph, what is the summation of chromatic number and matching number?

For the following graph, what is the summation of chromatic number and matching number?

GO Classes

422 views

GO Classes asked May 11, 2022

2 votes

1 answer

127

GO Classes Test Series 2024 | Discrete Mathematics | Test 5 | Question: 18
Which of the following statements about simple graphs are true ? Two complete graphs on $m,n$ vertices respectively, are isomorphic to each other if and only if $m=n.$ Wheel graph on $n$ vertices, $n \geq 4,$ is never ... always planar graph. Complement of a cycle graph on $n$ vertices is connected if and only if $n \geq 5.$

Which of the following statements about simple graphs are true ?Two complete graphs on $m,n$ vertices respectively, are isomorphic to each other if and only if $m=n.$Whee...

GO Classes

394 views

GO Classes asked May 11, 2022

2 votes

1 answer

128

GO Classes Test Series 2024 | Discrete Mathematics | Test 5 | Question: 22
Which of the following statements are correct? The complement of a simple disconnected graph must be connected. The complement of a simple connected graph must be disconnected. The complement of complete bipartite graph $\text{K}(4,6)$ ... . Then $\text{G}$ must have $4k$ or $4k + 1$ vertices for some integer $k.$

Which of the following statements are correct?The complement of a simple disconnected graph must be connected.The complement of a simple connected graph must be disconnec...

GO Classes

276 views

GO Classes asked May 11, 2022

3 votes

1 answer

129

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

637 views

GO Classes asked May 11, 2022

0 votes

1 answer

130

What is the number of faces in a connected plane graph having 23 vertices, 30 edges?
What is the number of faces in a connected plane graph having 23 vertices, 30 edges?

What is the number of faces in a connected plane graph having 23 vertices, 30 edges?

R S BAGDA

296 views

R S BAGDA asked Apr 27, 2022

19 votes

5 answers

131

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.9k views

Arjun asked Feb 15, 2022

14 votes

3 answers

132

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.6k views

Arjun asked Feb 15, 2022

14 votes

2 answers

133

GATE CSE 2022 | Question: 40
The following simple undirected graph is referred to as the Peterson graph. Which of the following statements is/are $\text{TRUE}?$ The chromatic number of the graph is $3.$ The graph has a Hamiltonian path. The following graph is isomorphic to the Peterson ... $3.$ (A subset of vertices of a graph form an independent set if no two vertices of the subset are adjacent.)

The following simple undirected graph is referred to as the Peterson graph.Which of the following statements is/are $\text{TRUE}?$The chromatic number of the graph is $3....

Arjun

7.6k views

Arjun asked Feb 15, 2022

16 votes

4 answers

134

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.5k views

Arjun asked Feb 15, 2022

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