The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
GATE Overflow
Facebook Login
Google Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
All Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous
Blogs
New Blog
Exams
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions.
Recent questions and answers in Graph Theory
0
votes
2
answers
1
PGEE 2018
Maximal Independence Number is the cardinality of maximal independence set ( Independence set V of graph G is set in which no vertex of the set have a direct edge between them). 1) Maximal Independence Number of a complete graph is n1 2) Maximal Independence ... Maximal Independence Number of a complete graph is 1 4) Maximal Independence Number of complete graph is $\geq \frac{n}{2}$
answered
6 hours
ago
in
Graph Theory
by
abhishekmehta4u
Loyal
(
9.7k
points)

21
views
graphtheory
iiithpgee
+1
vote
1
answer
2
PGEE 2018
Consider Undirected Graph G having vertex V {A,B,C,D,E} and edge pair as E {AB BD BE AC CE CD} A) Given graph is disconnected B) Given graph is complete C) Given graph has vertex connectivity 2 D) Given graph has edge connectivity 1
answered
6 hours
ago
in
Graph Theory
by
abhishekmehta4u
Loyal
(
9.7k
points)

17
views
iiithpgee
graphtheory
0
votes
1
answer
3
IIT Kanpur Sample Test Paper
Given an undirected graph with vertices as your friends and edges between people who do not talk to each other. Your task is to invite as many guests to your party such that there are no two friends at the party who have problem talking to each ... instance of: A. Maximum vertex cover. B. Maximum cut. C. Maximum eigenvalue of adjacency matrix. D. None of the above.
answered
4 days
ago
in
Graph Theory
by
Mk Utkarsh
Boss
(
11.9k
points)

53
views
iitkanpur
writtentest
+1
vote
1
answer
4
CMI2010A06
A simple graph is one with no selfloops or multiple edges. Among the simple graphs with n vertices and at most 20n − 3 edges: There is always a graph with all vertices connected to at least 42 other vertices. For all such graphs the number of ... for some constant $c < 1$. There are no graphs with each vertex connected to at most 38 other vertices. None of the above
answered
4 days
ago
in
Graph Theory
by
Mk Utkarsh
Boss
(
11.9k
points)

86
views
cmi2010
graphtheory
0
votes
2
answers
5
CMI2017B5
An undirected graph is connected if, for any two vertices {u, v} of the graph, there is a path in the graph starting at u and ending at v. A tree is a connected, undirected graph that contains no cycle. (a) A leaf in a tree is a vertex that has degree 1. Prove that ... that is, u ∈ V1 and v ∈ V2 or vice versa. Prove that if G is a tree with at least two vertices, then G is bipartite.
answered
5 days
ago
in
Graph Theory
by
Mk Utkarsh
Boss
(
11.9k
points)

85
views
cmi2017
graphtheory
+1
vote
1
answer
6
Narsingh Deo Problem 228
answered
5 days
ago
in
Graph Theory
by
Kushagra Chatterjee
Junior
(
827
points)

46
views
graphtheory
narsingh
deo
+9
votes
2
answers
7
TIFR2018A9
How many ways are there to assign colours from range $\left\{1,2,...,r\right\}$ to vertices of the following graph so that adjacent vertices receive distinct colours? $r^{4}$ $r^{4}  4r^{3}$ $r^{4}5r^{3}+8r^{2}4r$ $r^{4}4r^{3}+9r^{2}3r$ $r^{4}5r^{3}+10r^{2}15r$
answered
5 days
ago
in
Graph Theory
by
Sourav Basu
Active
(
1.4k
points)

278
views
tifr2018
graphtheory
graphcoloring
+14
votes
6
answers
8
TIFR2015B5
Suppose $\begin{pmatrix} 0&1 &0&0&0&1 \\ 1&0&1&0&0&0 \\ 0&1&0&1&0&1 \\ 0&0&1&0&1&0 \\ 0&0&0&1&0&1 \\ 1&0&1&0&1&0 \end{pmatrix}$ is the adjacency matrix of an ... below has the above adjacency matrix? Only $(i)$ Only $(ii)$ Only $(iii)$ Only $(iv)$ $(i)$ and $(ii)$
answered
6 days
ago
in
Graph Theory
by
Hitesh
(
369
points)

572
views
tifr2015
graphconnectivity
graphtheory
0
votes
1
answer
9
Show that the two graphs are isomorphic (Narsingh Deo)
answered
6 days
ago
in
Graph Theory
by
Hitesh
(
369
points)

16
views
graphtheory
narsingh
deo
graphisomorphism
+1
vote
1
answer
10
What are the relevant chapters for GATE from the Graph Theory book by Narsingh Deo?
answered
6 days
ago
in
Graph Theory
by
Mk Utkarsh
Boss
(
11.9k
points)

107
views
graphtheory
engineeringmathematics
narsingh
deo
+1
vote
1
answer
11
Graph Theory
Let G be a simple graph in which every vertex has degree 3. Prove that G decomposes into claws iff G is bipartite.
answered
6 days
ago
in
Graph Theory
by
Kushagra Chatterjee
Junior
(
827
points)

13
views
graphtheory
discretemathematics
+28
votes
4
answers
12
GATE200671
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 vertices of degree zero in $G$ is: $1$ $n$ $n + 1$ $2^n$
answered
Apr 14
in
Graph Theory
by
JPranavc
(
225
points)

2.7k
views
gate2006
graphtheory
normal
degreeofgraph
+1
vote
3
answers
13
PGEE 2017
Consider a graph where vertex having number 2 to 12 (including 2 and 12), there is an edge between two vertex x and y iff x divides y Find number of strongly connected components
answered
Apr 13
in
Graph Theory
by
Sandy Sharma
(
235
points)

200
views
iiithpgee
graphtheory
connectedcomponents
+3
votes
2
answers
14
True/False
Which of the following statements related to graphs are True? Minimum Spanning Tree has ALWAYS Minimum weight edge included in it. Minimum Spanning Tree MIGHT have Maximum weight edge weight included in it. Maximum Spanning Tree has ALWAYS Maximum weight edge included ... edge included in it. Longest path from source to destination MAY OR MAY NOT have Maximum weight edge included in it.
answered
Apr 12
in
Graph Theory
by
Digvijay Pandey
Veteran
(
54.7k
points)

79
views
graphs
graphalgorithms
algorithms
0
votes
0
answers
15
Number of Possible Trees
How many total Homeomorphically Irreducible Trees are possible with 'n' nodes ?
asked
Apr 11
in
Graph Theory
by
ankitgupta.1729
Active
(
4.2k
points)

17
views
graphtheory
discretemathematics
trees
+1
vote
1
answer
16
CMI2011B01a
A multinational company is developing an industrial area with many buildings. They want to connect the buildings with a set of roads so that: Each road connects exactly two buildings. Any two buildings are connected via a sequence of roads. Omitting any road ... it always possible to colour each building with either red or blue so that every road connects a red and blue building?
answered
Apr 11
in
Graph Theory
by
Kushagra Chatterjee
Junior
(
827
points)

51
views
cmi2011
descriptive
graphcoloring
+1
vote
1
answer
17
CMI2011B02b
Let $G$ be a connected graph. For a vertex $x$ of $G$ we denote by $G−x$ the graph formed by removing $x$ and all edges incident on $x$ from $G$. $G$ is said to be good if there are at least two distinct vertices $x, y$ in $G$ such that both $G − x$ and $G − y$ are connected. Given a good graph, devise a linear time algorithm to find two such vertices.
answered
Apr 11
in
Graph Theory
by
Kushagra Chatterjee
Junior
(
827
points)

62
views
descriptive
cmi2011
graphtheory
graphconnectivity
+2
votes
1
answer
18
CMI2010B02
Let $G$ be a graph in which each vertex has degree at least $k$. Show that there is a path of length $k$ in $G$—that is, a sequence of $k+1$ distinct vertices $v_0, v_1, \dots v_k$ such that for $0 \leq i < k,$ $v_i$ is connected to $v_{i+1}$ in $G$.
answered
Apr 9
in
Graph Theory
by
Kushagra Chatterjee
Junior
(
827
points)

62
views
cmi2010
descriptive
graphtheory
graphconnectivity
+2
votes
1
answer
19
CMI2010B01a
An international cellphone company provides service on 7 different frequencies. They wish to set up business in Tamil Nadu and have fixed the locations of 100 towers for their new service. The company has to ensure that two towers broadcasting on the same frequency are at least 100 km apart, so that there is no interference of signals. Model this problems using graphs.
answered
Apr 9
in
Graph Theory
by
Kushagra Chatterjee
Junior
(
827
points)

35
views
cmi2010
descriptive
graphtheory
0
votes
1
answer
20
#Graph Theory Any Simple way to prove this ?
answered
Apr 9
in
Graph Theory
by
asriv
Active
(
1.1k
points)

50
views
graphtheory
discrete
discretemathematics
+1
vote
1
answer
21
Discrete Mathematics By Kenneth H Rosen
How to Find Whether Given Graph is NonPlanar using Kuratwoski's Theorem ?
answered
Apr 6
in
Graph Theory
by
Hitesh
(
369
points)

27
views
kennethrosen
discretemathematics
graphtheory
0
votes
1
answer
22
Graph Theory
Consider the following undirected graph with some edge costs missing. Suppose the wavy edges form a Minimum Cost Spanning Tree for $G$. Then, which of the following inequalities NEED NOT hold? $cost(a,b)\geq 6$. $cost(b,e)\geq 5$. $cost(e,f)\geq 5$. $cost(a,d)\geq 4$. $cost(b,c)\geq 4$. Please someone solve and explain :)
answered
Apr 6
in
Graph Theory
by
abhishekmehta4u
Loyal
(
9.7k
points)

54
views
graphtheory
discretemathematics
graphconnectivity
+1
vote
1
answer
23
Graph Theory
Can someone solve this? Also please attempt this question on Algorithms time complexity if interested :) https://gateoverflow.in/210836/algorithmstimecomplexity
answered
Apr 5
in
Graph Theory
by
abhishekmehta4u
Loyal
(
9.7k
points)

50
views
graphtheory
discretemathematics
graphconnectivity
0
votes
1
answer
24
related to gate previous year
can some give example where cardinality of mincut will be < mindegree of the graph I found in question they have mentioned its <= , but i dont see any case where it is < https://gateoverflow.in/1504/gate1999_5
[closed]
answered
Apr 5
in
Graph Theory
by
Ananya Jaiswal 1
Active
(
1.2k
points)

17
views
+5
votes
3
answers
25
GATE1992_02,viii
Choose the correct alternatives ( more than one may be correct) and write the corresponding letters only: (viii) A nonplanar graph with minimum number of vertices has (a) 9 edges, 6 vertices (b) 6 edges, 4 vertices (c) 10 edges, 5 vertices (d) 9 edges, 5 vertices
answered
Apr 3
in
Graph Theory
by
sourav.
Boss
(
15.8k
points)

414
views
gate1992
graphtheory
normal
graphplanarity
outofsyllabusnow
+23
votes
2
answers
26
GATE20012.15
How many undirected graphs (not necessarily connected) can be constructed out of a given set $V=\{v_1, v_2, \dots v_n\}$ of $n$ vertices? $\frac{n(n1)} {2}$ $2^n$ $n!$ $2^\frac{n(n1)} {2} $
answered
Apr 1
in
Graph Theory
by
mehul vaidya
Junior
(
593
points)

2.3k
views
gate2001
graphtheory
normal
counting
+1
vote
1
answer
27
UGC NET NOV 2017 PAPER 2 Q5
5. Consider the graph given below : Use Kruskal’s algorithm to find a minimal spanning tree for the graph. The List of the edges of the tree in the order in which they are choosen is ? (1) AD, AE, AG, GC, GB, BF (2) GC, GB, BF, GA, AD, AE (3) GC, AD, GB, GA, BF, AE (4) AD, AG, GC, AE, GB, BF
answered
Mar 30
in
Graph Theory
by
Sukanya Das
Boss
(
11.2k
points)

89
views
ugcnetnov2017ii
0
votes
0
answers
28
Graph Theory By Narsingh Deo
Where can I find solutions to Narsingh Deo Book for Graph theory any online links and pdf will be helpful ?
asked
Mar 26
in
Graph Theory
by
Sayed Athar
(
93
points)

45
views
+21
votes
4
answers
29
TIFR2017B12
An undirected graph is complete if there is an edge between every pair of vertices. Given a complete undirected graph on $n$ vertices, in how many ways can you choose a direction for the edges so that there are no directed cycles? $n$ $\frac{n(n1)}{2}$ $n!$ $2^n$ $2^m, \: \text{ where } m=\frac{n(n1)}{2}$
answered
Mar 26
in
Graph Theory
by
Pawan Kumar 2
Active
(
4.4k
points)

918
views
tifr2017
graphtheory
counting
0
votes
0
answers
30
Graph Theory
Walk : Vertices may repeat. Edges may repeat (Closed or Open) Trail : Vertices may repeat. Edges cannot repeat (Open) Circuit : Vertices may repeat. Edges cannot repeat (Closed) Path : Vertices cannot repeat. Edges cannot repeat (Open) Cycle : Vertices cannot repeat. Edges cannot repeat (Closed) Can someone verify these terminologies? They are pretty confusing :/
asked
Mar 26
in
Graph Theory
by
gauravkc
Active
(
4.9k
points)

45
views
graphtheory
discretemathematics
engineeringmathematics
+1
vote
1
answer
31
Graph theory
As a triangle graph is $2 $ connected, thus for a given triangle graph, $r= 2( r_1\text{ and } r_2)$ , $k=2, e = 3, v=3$, but it still doesn't satisfy the equation, Can someone tell me where did I go wrong? Thanks
answered
Mar 25
in
Graph Theory
by
abhishekmehta4u
Loyal
(
9.7k
points)

84
views
graphtheory
0
votes
0
answers
32
[Graphs]IITk Written test
Graph Matching was explained. Let $S$ and $R$ be the matching graph, then a new graph $G=(SR) \cup (RS)$, will be union of vertex disjoint path and cycle. Also prove that the cycle obtained will be of even length.
asked
Mar 19
in
Graph Theory
by
rahul sharma 5
Boss
(
23k
points)

67
views
iitkanpur
writtentest
mtech
gate2017
+2
votes
0
answers
33
[Graphs]IITk Written test
if degree of vertices < 3, then prove that the graph will be union of vertex disjoint path and cycle
asked
Mar 19
in
Graph Theory
by
rahul sharma 5
Boss
(
23k
points)

61
views
iitkanpur
writtentest
interview
mtech
gate2017
0
votes
1
answer
34
Rosen (Graph)
Show that an edge in a simple graph is a cut edge if and only if this edge is not a part of any simple circuit in the graph.
answered
Mar 18
in
Graph Theory
by
Kaluti
Loyal
(
5.3k
points)

49
views
discretemathematics
graphtheory
0
votes
1
answer
35
GraphTheory_Problem_testpaper
Consider the undirected graph $G$ defined as follows. The vertices of $G$ are bits of strings of length $n$. We have an edge between vertex $u$ and $v$ if and only if $u$ and $v$ differ exactly in one bit position. The ratio of chromatic number of $G$ to the diameter of $G$ is . $\dfrac{1}{(2^{n1})}$ $\dfrac{1}{n}$ $\dfrac{2}{n}$ $\dfrac{3}{n}$
[closed]
answered
Mar 17
in
Graph Theory
by
Kaluti
Loyal
(
5.3k
points)

57
views
graphtheory
graphcoloring
+1
vote
1
answer
36
Graph Theory: Degree of a region
In the given following planar graph, what is the degree of the region R1:
answered
Mar 12
in
Graph Theory
by
MayankSharma
(
121
points)

178
views
graphtheory
discretemathematics
+7
votes
5
answers
37
GATE201818
The chromatic number of the following graph is _____
answered
Mar 8
in
Graph Theory
by
Sukanya Das
Boss
(
11.2k
points)

1.2k
views
gate2018
graphtheory
chromaticnumber
numericalanswers
0
votes
0
answers
38
UGC NET DEC 14 PAPER 2 Q  45
45. Which one of the following is used to compute cyclomatic complexity ? (A) The number of regions – 1 (B) E – N + 1, where E is the number of flow graph edges and N is the number of flow graph nodes. (C) P – 1, where P is the number of predicate nodes in the flow graph G. (D) P + 1, where P is the number of predicate nodes in the flow graph G.
[closed]
asked
Mar 8
in
Graph Theory
by
kavikeve
(
459
points)

42
views
ugcnetdec2014ii
0
votes
3
answers
39
Planar graph
The total number of planar graphs can be formed with 5 vertices are _____
answered
Mar 6
in
Graph Theory
by
Mk Utkarsh
Boss
(
11.9k
points)

204
views
graphtheory
0
votes
1
answer
40
Rosen (Graphs)
How much storage is needed to represent a simple graph with n vertices and m edges using. a) adjacency lists? b) an adjacency matrix? c) an incidence matrix?
answered
Mar 1
in
Graph Theory
by
Tesla!
Boss
(
15.3k
points)

89
views
graphtheory
kennethrosen
To see more, click for all the
questions in this category
.
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
Members at the site
shubham lata 1
sonveer tomar 1
Shubhgupta
abhishekmehta4u
Aditya Tewari
utk0203
Amey Umarekar
Lakshman Patel RJIT
Recent Posts
OS resources
All the Best to ISRO SC WRitten Test candidates
About new iits
barc result
Suggestion for IIITH exam
All categories
General Aptitude
1.2k
Engineering Mathematics
5k
Discrete Mathematics
3.4k
Mathematical Logic
1.4k
Set Theory & Algebra
886
Combinatory
609
Graph Theory
578
Probability
623
Linear Algebra
507
Calculus
369
Digital Logic
2k
Programming & DS
3.6k
Algorithms
3k
Theory of Computation
3.9k
Compiler Design
1.5k
Operating System
2.8k
Databases
2.9k
CO & Architecture
2.5k
Computer Networks
2.9k
Non GATE
949
Others
1.3k
Admissions
412
Exam Queries
419
Tier 1 Placement Questions
17
Job Queries
55
Projects
9
Follow @csegate
Gatecse
Recent questions and answers in Graph Theory
Recent Blog Comments
Thank you, Sir!
@
Question 1 and 2 of sample paper section 2 were ...
Direct questions from sample paper?That's ...
Not only GATE, they even gave questions from the ...
34,814
questions
41,801
answers
119,032
comments
41,445
users