Login
Register
@
Dark Mode
Profile
Edit my Profile
Messages
My favorites
Register
Activity
Q&A
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous Years
Blogs
New Blog
Exams
Dark Mode
Recent questions and answers in Graph Theory
0
votes
1
answer
1
DISCRETE
Let T be a tree with n vertices and k be the maximum size of an independent set in T. Then the size of maximum matching in T is (A) k (B) n−k (C) (n−1)/2
ks824
answered
in
Graph Theory
Feb 21
by
ks824
444
views
graph-matching
0
votes
1
answer
2
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$
minip
answered
in
Graph Theory
Feb 17
by
minip
1.8k
views
gatecse2024-set1
multiple-selects
graph-theory
1
vote
2
answers
3
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 __________.
Deepak Poonia
answered
in
Graph Theory
Feb 16
by
Deepak Poonia
1.6k
views
gatecse2024-set2
graph-theory
numerical-answers
2
votes
2
answers
4
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}$
ankitgupta.1729
answered
in
Graph Theory
Feb 16
by
ankitgupta.1729
2.5k
views
gatecse2024-set2
graph-theory
1
vote
0
answers
5
Gate 2016
The minimum number of colours that is sufficient to vertex-colour any planar graph is ________. I am confused with the question's language. please correct me if I have a wrong assumption. We need to tell the minimum colors required for a planar graph. Suppose I start ... is only fixed to 4. I understand the answer not to be less than 4. What does the word "any" means here?
TusharRana
asked
in
Graph Theory
Feb 8
by
TusharRana
175
views
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
GO Classes
answered
in
Graph Theory
Feb 5
by
GO Classes
550
views
goclasses2024-mockgate-14
graph-theory
degree-of-graph
multiple-selects
1-mark
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?$
GO Classes
answered
in
Graph Theory
Feb 5
by
GO Classes
488
views
goclasses2024-mockgate-14
numerical-answers
graph-theory
graph-connectivity
2-marks
1
vote
0
answers
8
Memory Based GATE DA 2024 | Question: 64
Minimum Number of colors in concentric circles.
GO Classes
asked
in
Graph Theory
Feb 4
by
GO Classes
110
views
gate2024-da-memory-based
goclasses
graph-theory
graph-coloring
1
vote
1
answer
9
#self doubt
In the above figure, how many topological sorts are possible, I tried the following method, if we include 5 _ _ _ _ _ for 5 space 5c3 for (2,3,1) then 2 position is 4,0 so a total of 10 if we do like 4 5 _ _ _ _ then only ... GFG the total possible sorts are 13 can someone why this difference is coming ? https://www.geeksforgeeks.org/all-topological-sorts-of-a-directed-acyclic-graph/
Mrityudoot
answered
in
Graph Theory
Feb 1
by
Mrityudoot
122
views
discrete-mathematics
3
votes
1
answer
10
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)
SankarVinayak
answered
in
Graph Theory
Jan 29
by
SankarVinayak
405
views
goclasses2024-mockgate-13
goclasses
graph-theory
vertex-cover
2-marks
4
votes
1
answer
11
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?
GO Classes
answered
in
Graph Theory
Jan 21
by
GO Classes
568
views
goclasses2024-mockgate-12
goclasses
numerical-answers
graph-theory
graph-coloring
2-marks
14
votes
3
answers
12
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$
Quantum City
answered
in
Graph Theory
Jan 15
by
Quantum City
7.3k
views
gatecse-2022
graph-theory
graph-connectivity
2-marks
3
votes
1
answer
13
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?
GO Classes
answered
in
Graph Theory
Jan 13
by
GO Classes
404
views
goclasses2024-mockgate-11
goclasses
numerical-answers
graph-theory
1-mark
0
votes
0
answers
14
Consider a weighted undirected graph with positive edge weights and let (u, v) be an [2] edge in the graph. It is known that the shortest path from source vertex r to u has weight 53 and shortest path from r to v has weight 65. Which statement is always true?
Malusi
asked
in
Graph Theory
Jan 12
by
Malusi
81
views
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
ks2003
answered
in
Graph Theory
Jan 9
by
ks2003
400
views
isro-2024
discrete-mathematics
graph-theory
0
votes
1
answer
16
A tree has 2n vertices of degree 1, 3n vertices of degree 2 and n vertices of degree 3. Determine the number of vertices and edges in the tree.
Hira Thakur
answered
in
Graph Theory
Jan 7
by
Hira Thakur
218
views
graph-connectivity
0
votes
1
answer
17
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)}$
Dadu
answered
in
Graph Theory
Jan 7
by
Dadu
171
views
isro-2024
graph-theory
discrete-mathematics
0
votes
1
answer
18
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
Hira Thakur
answered
in
Graph Theory
Jan 7
by
Hira Thakur
255
views
isro-2024
graph-theory
graph-planarity
0
votes
0
answers
19
Made easy test series
Consider a strongly connected directed graph G(V, F), where |V| = 101. The minimum possible value of IEl is
abhishekbhingarde
asked
in
Graph Theory
Jan 6
by
abhishekbhingarde
95
views
86
votes
8
answers
20
GATE CSE 2004 | Question: 79
How many graphs on $n$ labeled vertices exist which have at least $\frac{(n^2 - 3n)}{ 2}$ edges ? $^{\left(\frac{n^2-n}{2}\right)}C_{\left(\frac{n^2-3n} {2}\right)}$ $^{{\large\sum\limits_{k=0}^{\left (\frac{n^2-3n}{2} \right )}}.\left(n^2-n\right)}C_k$ $^{\left(\frac{n^2-n}{2}\right)}C_n$ $^{{\large\sum\limits_{k=0}^n}.\left(\frac{n^2-n}{2}\right)}C_k$
USharma02
answered
in
Graph Theory
Dec 21, 2023
by
USharma02
14.2k
views
gatecse-2004
graph-theory
combinatory
normal
counting
1
vote
0
answers
21
Made Easy: Counting number of subgraphs of the given graph. How should I approach this question?
tishhaagrawal
asked
in
Graph Theory
Dec 16, 2023
by
tishhaagrawal
489
views
gate-preparation
test-series
made-easy-test-series
self-doubt
counting
graph-theory
discrete-mathematics
graph-connectivity
0
votes
1
answer
22
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
Biswajit Kumar
answered
in
Graph Theory
Dec 15, 2023
by
Biswajit Kumar
342
views
graph-theory
0
votes
0
answers
23
Find the MIS and MaxIS
Dknights
asked
in
Graph Theory
Dec 14, 2023
by
Dknights
125
views
graph-theory
0
votes
1
answer
24
#self doubt
Domination set and MIS are the same?
ajayraho
answered
in
Graph Theory
Dec 14, 2023
by
ajayraho
110
views
graph-theory
43
votes
8
answers
25
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}$
Ray Tomlinson
answered
in
Graph Theory
Nov 28, 2023
by
Ray Tomlinson
8.5k
views
gatecse-2006
graph-theory
normal
graph-connectivity
2
votes
1
answer
26
TIFR CSE 2023 | Part B | Question: 13
You have a regular tetrahedron and $4$ distinct colours. You wish to paint the faces of the tetrahedron such that each face gets a different colour. How many ways can you colour the tetrahedron? Recall that a regular tetrahedron is a three-dimensional ... considered the same if they are identical after possibly rotating the tetrahedron. $24$ $12$ $8$ $6$ $2$
psnt_rwt
answered
in
Graph Theory
Nov 14, 2023
by
psnt_rwt
453
views
tifr2023
graph-theory
graph-coloring
0
votes
0
answers
27
#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.
Dknights
asked
in
Graph Theory
Nov 13, 2023
by
Dknights
177
views
graph-theory
0
votes
0
answers
28
made easy test series
Suppose A is a 12 by 9 incidence matrix from a connected (but unknown) graph with 12 edges and 9 nodes. Then how many columns of A are independent? what this question want to ask can someone help me {hint}
jugnu1337
asked
in
Graph Theory
Nov 12, 2023
by
jugnu1337
173
views
made-easy-test-series
0
votes
1
answer
29
#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
prajjwal_191
answered
in
Graph Theory
Nov 10, 2023
by
prajjwal_191
233
views
graph-theory
2
votes
1
answer
30
Chromatic Number
Abhay123
answered
in
Graph Theory
Oct 19, 2023
by
Abhay123
192
views
graph-theory
graph-coloring
0
votes
1
answer
31
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.)
Abhay123
answered
in
Graph Theory
Oct 19, 2023
by
Abhay123
297
views
self-doubt
graph-theory
discrete-mathematics
100
votes
10
answers
32
GATE CSE 2014 Set 1 | Question: 51
Consider an undirected graph $G$ where self-loops are not allowed. The vertex set of $G$ is $\{(i,j) \mid1 \leq i \leq 12, 1 \leq j \leq 12\}$. There is an edge between $(a,b)$ and $(c,d)$ if $|a-c| \leq 1$ and $|b-d| \leq 1$. The number of edges in this graph is______.
akshay_123
answered
in
Graph Theory
Oct 14, 2023
by
akshay_123
26.5k
views
gatecse-2014-set1
graph-theory
numerical-answers
normal
graph-connectivity
64
votes
9
answers
33
GATE IT 2006 | Question: 25
Consider the undirected graph $G$ defined as follows. The vertices of $G$ are bit strings of length $n$. We have an edge between vertex $u$ and vertex $v$ if and only if $u$ and $v$ differ in exactly one bit position (in other words, $v$ can be obtained from $u$ by ... $\left(\frac{1}{n}\right)$ $\left(\frac{2}{n}\right)$ $\left(\frac{3}{n}\right)$
akshay_123
answered
in
Graph Theory
Oct 14, 2023
by
akshay_123
13.0k
views
gateit-2006
graph-theory
graph-coloring
normal
26
votes
4
answers
34
GATE CSE 1993 | Question: 8.1
Consider a simple connected graph $G$ with $n$ vertices and $n$ edges $(n > 2)$. Then, which of the following statements are true? $G$ has no cycles The graph obtained by removing any edge from $G$ is not connected $G$ has at least one cycle The graph obtained by removing any two edges from $G$ is not connected None of the above
akshay_123
answered
in
Graph Theory
Oct 9, 2023
by
akshay_123
9.7k
views
gate1993
graph-theory
graph-connectivity
easy
multiple-selects
51
votes
4
answers
35
GATE CSE 1991 | Question: 01,xv
The maximum number of possible edges in an undirected graph with $n$ vertices and $k$ components is ______.
akshay_123
answered
in
Graph Theory
Oct 9, 2023
by
akshay_123
11.4k
views
gate1991
graph-theory
graph-connectivity
normal
fill-in-the-blanks
49
votes
11
answers
36
GATE CSE 2009 | Question: 2
What is the chromatic number of an $n$ vertex simple connected graph which does not contain any odd length cycle? Assume $n > 2$. $2$ $3$ $n-1$ $n$
akshay_123
answered
in
Graph Theory
Oct 8, 2023
by
akshay_123
13.0k
views
gatecse-2009
graph-theory
graph-coloring
normal
1
vote
1
answer
37
Graph Theory
Abhay123
answered
in
Graph Theory
Oct 8, 2023
by
Abhay123
178
views
graph-theory
discrete-mathematics
graph-coloring
36
votes
4
answers
38
GATE CSE 2014 Set 1 | Question: 52
An ordered $n-$tuple $(d_1, d_2,\ldots,d_n)$ with $d_1 \geq d_2 \geq \ldots \geq d_n$ is called graphic if there exists a simple undirected graph with $n$ vertices having degrees $d_1,d_2,\ldots,d_n$ respectively. Which one of the following $6$-tuples is NOT graphic? $(1,1,1,1,1,1)$ $(2,2,2,2,2,2)$ $(3,3,3,1,0,0)$ $(3,2,1,1,1,0)$
akshay_123
answered
in
Graph Theory
Oct 8, 2023
by
akshay_123
7.3k
views
gatecse-2014-set1
graph-theory
normal
degree-of-graph
111
votes
9
answers
39
GATE CSE 2012 | Question: 38
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 $15$ $30$ $90$ $360$
akshay_123
answered
in
Graph Theory
Oct 7, 2023
by
akshay_123
34.6k
views
gatecse-2012
graph-theory
normal
marks-to-all
counting
58
votes
7
answers
40
GATE IT 2008 | Question: 4
What is the size of the smallest $\textsf{MIS}$ (Maximal Independent Set) of a chain of nine nodes? $5$ $4$ $3$ $2$
꧁༒☬ĿọŗԀ 🆂🅷🅸🆅🅰☬༒꧂
answered
in
Graph Theory
Sep 25, 2023
by
꧁༒☬ĿọŗԀ 🆂🅷🅸🆅🅰☬༒꧂
49.5k
views
gateit-2008
normal
graph-connectivity
To see more, click for all the
questions in this category
.
Subscribe to GATE CSE 2024 Test Series
Subscribe to GO Classes for GATE CSE 2024
Quick search syntax
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
Recent Posts
Post GATE 2024 Guidance [Counseling tips and resources]
GATE CSE 2024 Result Responses
[Project Contest] Pytorch backend support for MLCommons Cpp Inference implementation
Participating in MLCommons Inference v4.0 submission (deadline is February 23 12pm IST)
IIITH PGEE 2024 Test Series by GO Classes
Subjects
All categories
General Aptitude
(3.5k)
Engineering Mathematics
(10.4k)
Discrete Mathematics
(7.1k)
Mathematical Logic
(2.5k)
Set Theory & Algebra
(1.9k)
Combinatory
(1.6k)
Graph Theory
(1.1k)
Probability
(1.4k)
Linear Algebra
(1.1k)
Calculus
(792)
Optimization
(0)
Digital Logic
(3.6k)
Programming and DS
(6.2k)
Algorithms
(4.8k)
Theory of Computation
(6.9k)
Compiler Design
(2.5k)
Operating System
(5.2k)
Databases
(4.8k)
CO and Architecture
(4.0k)
Computer Networks
(4.9k)
Artificial Intelligence
(79)
Machine Learning
(48)
Data Mining and Warehousing
(25)
Non GATE
(1.4k)
Others
(2.7k)
Admissions
(684)
Exam Queries
(1.6k)
Tier 1 Placement Questions
(17)
Job Queries
(80)
Projects
(11)
Unknown Category
(870)
64.3k
questions
77.9k
answers
244k
comments
80.0k
users
Recent questions and answers in Graph Theory
Recent Blog Comments
category ?
Hi @Arjun sir, I have obtained a score of 591 in ...
download here
Can you please tell about IIT-H mtech CSE self...
Please add your admission queries here:...