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

0 votes

1 answer

1

Practice Material Question
If G is a connected graph with 6 vertices and maximum number of edges, then which of the following is true ? (a) Euler path exists, but Euler circuit does not exist in G. (b) Only Euler path exists in G. (c) Euler circuit does not exists in G (d) G is not traversable.

If G is a connected graph with 6 vertices and maximum number of edges, then which of the following is true ? (a) Euler path exists, but Euler circuit does not exist in G....

Akash Chakraborty

87 views

Akash Chakraborty asked Mar 30

0 votes

1 answer

2

#algorithm
how many spanning trees are possible for complete graph of 4 vertices

how many spanning trees are possible for complete graph of 4 vertices

Amoljadhav

124 views

Amoljadhav asked Mar 1

2 votes

2 answers

3

GATE CSE 2024 | Set 2 | Question: 7
Let $\text{A}$ be the adjacency matrix of a simple undirected graph $\text{G}$. Suppose $\text{A}$ is its own inverse. Which one of the following statements is always TRUE? $\text{G}$ is a cycle $\text{G}$ is a perfect matching $\text{G}$ is a complete graph There is no such graph $\text{G}$

Let $\text{A}$ be the adjacency matrix of a simple undirected graph $\text{G}$. Suppose $\text{A}$ is its own inverse. Which one of the following statements i...

Arjun

2.8k views

Arjun asked Feb 16

1 votes

3 answers

4

GATE CSE 2024 | Set 2 | Question: 50
The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. The chromatic number of the following graph is __________.

The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. The chromatic number of the following graph is __________.

Arjun

1.8k views

Arjun asked Feb 16

0 votes

1 answer

5

GATE CSE 2024 | Set 1 | Question: 41
The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. Let $G$ be any graph with $n$ vertices and chromatic number $k$. Which of the following statements is/are always TRUE? $G$ contains a complete subgraph with ... $n/k$ $G$ contains at least $k(k-1) / 2$ edges $G$ contains a vertex of degree at least $k$

The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. Let $G$ be any graph with $n$ vertices and chromatic nu...

Arjun

2.0k views

Arjun asked Feb 16

13 votes

1 answer

6

GO Classes Test Series 2024 | Mock GATE | Test 14 | Question: 15
Let $\mathrm{G}$ be a simple undirected graph on 8 vertices such that there is a vertex of degree 1 , a vertex of degree 2 , a vertex of degree 3 , a vertex of degree 4, a vertex of degree 5 , a vertex of degree 6 and ... of degree 7. Which of the following can be the degree of the last vertex? (Select all that are possible) 0 3 4 8

Let $\mathrm{G}$ be a simple undirected graph on 8 vertices such that there is a vertex of degree 1 , a vertex of degree 2 , a vertex of degree 3 , a vertex of degree 4, ...

GO Classes

644 views

GO Classes asked Feb 5

6 votes

1 answer

7

GO Classes Test Series 2024 | Mock GATE | Test 14 | Question: 57
A strongly connected component $(\mathrm{SCC})$ of a directed graph $\mathrm{G}=(\mathrm{V}, \mathrm{E})$ ... ; edges in its associated directed acyclic graph $G^{\prime}$ be $A, B$ respectively, then what is $A+B?$

A strongly connected component $(\mathrm{SCC})$ of a directed graph $\mathrm{G}=(\mathrm{V}, \mathrm{E})$ is a maximal set of vertices such that any two vertices in the s...

GO Classes

546 views

GO Classes asked Feb 5

1 votes

0 answers

8

Memory Based GATE DA 2024 | Question: 64
Minimum Number of colors in concentric circles.

Minimum Number of colors in concentric circles.

GO Classes

132 views

GO Classes asked Feb 4

3 votes

1 answer

9

GO Classes Test Series 2024 | Mock GATE | Test 13 | Question: 63
For an undirected graph $G$, let $\overline{G}$ refer to the complement (a graph on the same vertex set as $G$, with $(i, j)$ as an edge in $\overline{G}$ if and only if it is not an edge in $G$ ). Consider the following ... is equivalent to (iii) and (v). (i) is equivalent to (ii) and (iv). (i) is equivalent to (ii) and (v)

For an undirected graph $G$, let $\overline{G}$ refer to the complement (a graph on the same vertex set as $G$, with $(i, j)$ as an edge in $\overline{G}$ if and only if ...

GO Classes

443 views

GO Classes asked Jan 28

4 votes

1 answer

10

GO Classes Test Series 2024 | Mock GATE | Test 12 | Question: 46
Assume the following graph is a labeled graph i.e. every vertex has a unique label. In how many ways can we color the following labeled graph $\mathrm{G}$ with six colors $\{R, G, B, W, Y, M\}$ such that no two adjacent vertices are assigned the same color?

Assume the following graph is a labeled graph i.e. every vertex has a unique label.In how many ways can we color the following labeled graph $\mathrm{G}$ with six colors ...

GO Classes

627 views

GO Classes asked Jan 21

3 votes

1 answer

11

GO Classes Test Series 2024 | Mock GATE | Test 11 | Question: 11
The figure above shows an undirected graph with six vertices. Enough edges are to be deleted from the graph in order to leave a spanning tree, which is a connected subgraph having the same six vertices and no cycles. How many edges must be deleted?

The figure above shows an undirected graph with six vertices. Enough edges are to be deleted from the graph in order to leave a spanning tree, which is a connected subgra...

GO Classes

439 views

GO Classes asked Jan 13

0 votes

1 answer

12

Made Easy Mock Test 2

Rohit Chakraborty

259 views

Rohit Chakraborty asked Jan 11

0 votes

1 answer

13

ISRO 2024
Maximum number of Simple graphs possible with $n$ vertices $2^{n(n-1)/2}$ $2^{(n-1)/2}$ $2^{n(n+1)/2}$ $2^{n(n+1)}$

Maximum number of Simple graphs possible with $n$ vertices$2^{n(n-1)/2}$$2^{(n-1)/2}$$2^{n(n+1)/2}$$2^{n(n+1)}$

Ramayya

182 views

Ramayya asked Jan 7

0 votes

1 answer

14

ISRO 2024
If there are five faces and nine vertices in an undirected planar graph, then number of edges is 14 6 12 None of the above

If there are five faces and nine vertices in an undirected planar graph, then number of edges is14612None of the above

Ramayya

285 views

Ramayya asked Jan 7

0 votes

2 answers

15

ISRO 2024
Which of the following are true? In a graph G with ‘n’ vertices and ‘e’ edges, sum of degrees of vertices = 2*e. Eccentricity of a connected graph can never be equal to radius of the graph Girth of a graph is the shortest cycle of the graph Graph with equal degree for all vertices is multigraph (i), (ii), (iii) (ii), (iii), (iv) (i), (iii), (iv) None of the above

Which of the following are true?In a graph G with ‘n’ vertices and ‘e’ edges, sum of degrees of vertices = 2*e.Eccentricity of a connected graph...

Ramayya

435 views

Ramayya asked Jan 7

0 votes

0 answers

16

Which study material to refer to so that one can solve the theory questions on Graphs topic asked in PYQs

I have not been able to answer many of the Graph theory questions, I feel my comprehension of the topic is inadequate, could someone guide me to some reference material I...

DhruvaKashyap

185 views

DhruvaKashyap asked Dec 29, 2023

1 votes

0 answers

17

Made Easy: Counting number of subgraphs of the given graph. How should I approach this question?

tishhaagrawal

532 views

tishhaagrawal asked Dec 16, 2023

0 votes

0 answers

18

Find the MIS and MaxIS

Dknights

135 views

Dknights asked Dec 14, 2023

0 votes

1 answer

19

#self doubt
Domination set and MIS are the same?

Domination set and MIS are the same?

Dknights

122 views

Dknights asked Dec 12, 2023

0 votes

1 answer

20

Regular and complete graph
which of the following statements is true: a complete graph is $(N-1)$ regular a $(N-1)$ regular is a complete graph

which of the following statements is true:a complete graph is $(N-1)$ regulara $(N-1)$ regular is a complete graph

Dknights

400 views

Dknights asked Dec 12, 2023

0 votes

0 answers

21

#self_doubt#pyq#graphtheory
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 the answer is 45 but for the following cases, what will be the answer? 1- if the graph is directed 2- if vertices are not labeled.

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 tothe answer is 45 but for ...

Dknights

186 views

Dknights asked Nov 13, 2023

0 votes

1 answer

22

#applied course
how many regions are in the above graph and please explain with region formula also. r=e-v+(c+1) my attempt is : r=5-5+2 r=2 but the rule is twice the no of boundary edges which is (5*2) = sum of region degrees which (4+5=9 ) can someone explain where the fault is

how many regions are in the above graph and please explain with region formula also.r=e-v+(c+1)my attempt is :r=5-5+2r=2but the rule is twice the no of boundary edges whi...

Dknights

247 views

Dknights asked Nov 9, 2023

0 votes

1 answer

23

made easy test series
Suppose A is a 12 by 9 incidence matrix from a connected (but unknown) graph with 9 nodes and 12 edges. The diagonal entries of $A^{T}.A$ give the number of edges into each node. Then, what is the sum of those diagonal entries ________.

Suppose A is a 12 by 9 incidence matrix from a connected (but unknown) graph with 9 nodes and 12 edges. The diagonal entries of $A^{T}.A$give the number of edges into eac...

jugnu1337

349 views

jugnu1337 asked Oct 22, 2023

0 votes

1 answer

24

Self doubt
How many simple directed (unweighted) graphs on the set of vertices {v0,v1,…v5} are there that have at most one edge between any pair of vertices? (That is, for two vertices a, b, only at most one of the edges (a, b) and (b, a) is in the graph.)

How many simple directed (unweighted) graphs on the set of vertices {v0,v1,…v5} are there that have at most one edge between any pair of vertices? (That is, for two ver...

Anand67222

319 views

Anand67222 asked Oct 14, 2023

1 votes

1 answer

25

Graph Theory

suryansh rajput

192 views

suryansh rajput asked Oct 2, 2023

0 votes

2 answers

26

Bipartite Graph doubt

Çșȇ ʛấẗẻ

254 views

Çșȇ ʛấẗẻ asked Aug 29, 2023

0 votes

0 answers

27

Graph Thoery

Çșȇ ʛấẗẻ

88 views

Çșȇ ʛấẗẻ asked Aug 28, 2023

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