Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Search results for graph-theory
2
votes
2
answers
41
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.9k
views
Arjun
asked
Feb 16
Graph Theory
gatecse2024-set2
graph-theory
+
–
46
votes
6
answers
42
GATE CSE 2002 | Question: 1.4
The minimum number of colours required to colour the vertices of a cycle with $n$ nodes in such a way that no two adjacent nodes have the same colour is $2$ $3$ $4$ $n-2 \left \lfloor \frac{n}{2} \right \rfloor+2$
The minimum number of colours required to colour the vertices of a cycle with $n$ nodes in such a way that no two adjacent nodes have the same colour is$2$$3$$4$$n-2 \lef...
Kathleen
11.2k
views
Kathleen
asked
Sep 15, 2014
Graph Theory
gatecse-2002
graph-theory
graph-coloring
normal
+
–
1
votes
3
answers
43
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.9k
views
Arjun
asked
Feb 16
Graph Theory
gatecse2024-set2
graph-theory
numerical-answers
+
–
40
votes
7
answers
44
GATE CSE 2010 | Question: 28
The degree sequence of a simple graph is the sequence of the degrees of the nodes in the graph in decreasing order. Which of the following sequences can not be the degree sequence of any graph? $7, 6, 5, 4, 4, 3, 2, 1$ $6, 6, 6, 6, 3, 3, 2, 2$ $7, 6, 6, 4, 4, 3, 2, 2$ $8, 7, 7, 6, 4, 2, 1, 1$ I and II III and IV IV only II and IV
The degree sequence of a simple graph is the sequence of the degrees of the nodes in the graph in decreasing order. Which of the following sequences can not be the degree...
gatecse
18.6k
views
gatecse
asked
Sep 21, 2014
Graph Theory
gatecse-2010
graph-theory
degree-of-graph
+
–
43
votes
8
answers
45
GATE CSE 2006 | Question: 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}$
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 set...
go_editor
8.8k
views
go_editor
asked
Apr 24, 2016
Graph Theory
gatecse-2006
graph-theory
normal
graph-connectivity
+
–
14
votes
2
answers
46
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
Graph Theory
gatecse-2022
graph-theory
graph-isomorphism
multiple-selects
2-marks
+
–
35
votes
6
answers
47
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
Graph Theory
gatecse-2021-set1
graph-theory
graph-connectivity
2-marks
+
–
13
votes
1
answer
48
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
660
views
GO Classes
asked
Feb 5
Graph Theory
goclasses2024-mockgate-14
graph-theory
degree-of-graph
multiple-selects
1-mark
+
–
0
votes
1
answer
49
ISI kolkata MTech CS 2019
Let $K_n$ denote the complete graph on $n$ vertices, with $n ≥ 3$, and let $u$, $v$, $w$ be three distinct vertices of $K_n$. Determine the number of distinct paths from $u$ to $v$ that do not contain the vertex $w$.
Let $K_n$ denote the complete graph on $n$ vertices, with $n ≥ 3$, and let $u$, $v$, $w$ be three distinct vertices of $K_n$. Determine the number of distinct paths fro...
suvasish114
50
views
suvasish114
asked
6 days
ago
Graph Theory
graph-theory
combinatory
isi2019-pcb-cs
+
–
0
votes
1
answer
50
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
105
views
Akash Chakraborty
asked
Mar 30
Graph Theory
gate-preparation
graph-theory
+
–
0
votes
1
answer
51
Made Easy Mock Test 2
Rohit Chakraborty
270
views
Rohit Chakraborty
asked
Jan 11
Mathematical Logic
graph-theory
made-easy-test-series
engineering-mathematics
+
–
0
votes
1
answer
52
Made Easy Test Series 2024
Suppose we have a directed graph G = (V,E) with V= {1, 2, ..., n} and Eis presented as an adjacency list. For each vertex u in V, out(u) is a list such that (u, v) in {1, 2, ... k). For each u in V, we wish to compute a corresponding list in(u) =such that in E ... take to construct the lists in(u), u in V, from the lists out(u), u in V? T(n) =O(n+m) B. T(n)= O(n(m+n))
Suppose we have a directed graph G = (V,E) with V= {1, 2, ..., n} and Eis presented as an adjacency list. For each vertex u in V, out(u) is a list such that (u, v) in {1,...
Ray Tomlinson
542
views
Ray Tomlinson
asked
Aug 9, 2023
Algorithms
made-easy-test-series
algorithms
made-easy-booklet
algorithm-design
time-complexity
linked-list
graph-theory
graph-algorithms
+
–
6
votes
1
answer
53
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
558
views
GO Classes
asked
Feb 5
Graph Theory
goclasses2024-mockgate-14
numerical-answers
graph-theory
graph-connectivity
2-marks
+
–
0
votes
1
answer
54
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
Graph Theory
gatecse2024-set1
multiple-selects
graph-theory
+
–
4
votes
1
answer
55
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
645
views
GO Classes
asked
Jan 21
Graph Theory
goclasses2024-mockgate-12
goclasses
numerical-answers
graph-theory
graph-coloring
2-marks
+
–
0
votes
1
answer
56
#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
136
views
Amoljadhav
asked
Mar 1
Algorithms
algorithms
data-structures
graph-theory
+
–
28
votes
6
answers
57
GATE CSE 2015 Set 2 | Question: 28
A graph is self-complementary if it is isomorphic to its complement. For all self-complementary graphs on $n$ vertices, $n$ is A multiple of 4 Even Odd Congruent to 0 $mod$ 4, or, 1 $mod$ 4.
A graph is self-complementary if it is isomorphic to its complement. For all self-complementary graphs on $n$ vertices, $n$ isA multiple of 4EvenOddCongruent to 0 $mod$ 4...
go_editor
13.7k
views
go_editor
asked
Feb 12, 2015
Graph Theory
gatecse-2015-set2
graph-theory
graph-isomorphism
out-of-syllabus-now
+
–
3
votes
1
answer
58
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
449
views
GO Classes
asked
Jan 28
Graph Theory
goclasses2024-mockgate-13
goclasses
graph-theory
vertex-cover
2-marks
+
–
3
votes
1
answer
59
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
450
views
GO Classes
asked
Jan 13
Graph Theory
goclasses2024-mockgate-11
goclasses
numerical-answers
graph-theory
1-mark
+
–
57
votes
11
answers
60
GATE CSE 2014 Set 3 | Question: 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$
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\r...
go_editor
18.4k
views
go_editor
asked
Sep 28, 2014
Graph Theory
gatecse-2014-set3
graph-theory
graph-connectivity
normal
+
–
Page:
« prev
1
2
3
4
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register