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

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
Recent questions tagged graph
0
votes
0
answers
1
Michael Sipser Edition 3 Exercise 0 Question 14 (Page No. 28)
Ramsey's theorem$:$ Let $G$ be a graph. A clique in $G$ is a subgraph in which every two nodes are connected by an edge. An anticlique also called an independent set, is a subgraph in which every two nodes are not connected ... graph with $n$ nodes contains either a clique or an anticlique with at least $\frac{1}{2}log_{2}n$ nodes.
asked
Apr 14, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59.3k
points)

37
views
michaelsipser
theoryofcomputation
graph
proof
0
votes
1
answer
2
Michael Sipser Edition 3 Exercise 0 Question 13 (Page No. 27)
Show that every graph with two or more nodes contains two nodes that have equal degrees.
asked
Apr 14, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59.3k
points)

31
views
michaelsipser
theoryofcomputation
graph
proof
0
votes
0
answers
3
Michael Sipser Edition 3 Exercise 0 Question 9 (Page No. 27)
Write a formal description of the following graph.
asked
Apr 13, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59.3k
points)

42
views
michaelsipser
theoryofcomputation
graph
easy
0
votes
0
answers
4
Michael Sipser Edition 3 Exercise 0 Question 8 (Page No. 26)
Consider the undirected graph G= (V, E) where V , the set of nodes, is {1, 2, 3, 4} and E, the set of edges, is {{1, 2}, {2, 3}, {1, 3}, {2, 4}, {1, 4}}. Draw the graph G. What are the degrees of each node? Indicate a path from node 3 to node 4 on your drawing of G.
asked
Apr 13, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59.3k
points)

21
views
michaelsipser
theoryofcomputation
graph
easy
0
votes
1
answer
5
selfdoubt
A graph with alternating edges and vertices is called a walk (we can repeat the number of vertices and edges any number of times) . A walk in which no edges are repeated is called a trial. A trial in which no vertices are repeated is called a path. A trial in which only the starting and ending vertices are repeated is called a circuit. Are the definitions correct??
asked
Mar 31, 2019
in
Graph Theory
by
Doraemon
Junior
(
791
points)

34
views
graph
0
votes
0
answers
6
Regular Graph
If a 2regular graph G has a perfect matching then which of the following is/are true? S1: G is a cycle of even length S2: Chromatic number of G is 2 S3: G is connected S4: Every component of G is an even cycle Options A) S1,S2 B)S2,S4 C)S3,S4 D)S1,S4
asked
Nov 6, 2018
in
Graph Theory
by
dan31
Junior
(
883
points)

144
views
graphtheory
discretemathematics
graph
0
votes
0
answers
7
Graph
$1)$How many different adjacency matrices does a graph with n vertices and E edges have? $2)$How many different adjacency lists does a graph with n vertices have?
asked
Oct 21, 2018
in
DS
by
Lakshman Patel RJIT
Veteran
(
59.3k
points)

93
views
datastructures
graph
+2
votes
0
answers
8
graph theory
The line graph L(G) of a simple graph G is defined as follows: · There is exactly one vertex v(e) in L(G) for each edge e in G. · For any two edges e and e' in G, L(G) has an edge between v(e) and v(e'), if and only if e and e'are incident with the ... is planar. (S) The line graph of a tree is a tree. I have doubt in option R . K4 then its also a planer . correct me if i am Wrong?
asked
Oct 9, 2018
in
Graph Theory
by
Smishra95
Active
(
1.4k
points)

39
views
line
graph
0
votes
1
answer
9
DFSArticulation Point and Bridges
I want to find the articulation point and bridges in the above graph. Further for each vertex $v$ I want to compute $v.low=$min $\left \{ v.d, w.d \right \}$ where $v.d$=discovery time of vertex v $w.d$=discovery time of ... someone help me with the values of v.low ? Because based on v.low I will be further able to solve articulation point and bridge problem.
asked
Aug 28, 2018
in
DS
by
Ayush Upadhyaya
Boss
(
29.2k
points)

68
views
graph
dfs
algorithms
0
votes
1
answer
10
Test Series
Are MST and shortest path tree identical? T/F? with reasoning.
asked
Dec 5, 2017
in
Algorithms
by
targate2018
Active
(
1.8k
points)

63
views
graph
graphtheory
mst
minimumspanningtrees
0
votes
1
answer
11
Ace Test Series: Graph Theory  Graph Connectivity
Need comment on these ! "Click on image"
asked
Nov 26, 2017
in
Graph Theory
by
saxena0612
Boss
(
11.9k
points)

109
views
acetestseries
wrongchoices
badquestions
graph
graphconnectivity
recurrence
0
votes
2
answers
12
UGCNETdec2009ii22
The number of edges in a complete graph of n vertices is (A) n (B) n(n – 1)/2 (C) n(n + 1)/2 (D) (n^2)/2
asked
Sep 17, 2017
in
Graph Theory
by
rishu_darkshadow
Loyal
(
7.3k
points)

152
views
ugcnetdec2009ii
graph
graphtheory
0
votes
1
answer
13
Consider the following graph L and find the bridges, if any
A) No bridge B) {d, e} C) {c, d} D) {c, d} and {c, f}
asked
Aug 18, 2017
in
DS
by
habedo007
Active
(
2.8k
points)

550
views
graph
bridges
+2
votes
1
answer
14
Graph
The problem of finding the set of vertices reachable from a given vertex in a graph can be solved in time A. O(V^2) B. O(V + E) C. O(VE) D. none of these
asked
Jul 15, 2017
in
Algorithms
by
Abhisek Saha
(
151
points)

74
views
graph
graphalgorithms
0
votes
4
answers
15
GateForum Test Series: Graph Theory  Graph Coloring
The Chromatic Number of Cycle Graph with 7 vertices _____
asked
Jan 9, 2017
in
Graph Theory
by
Jason GATE
Active
(
3.8k
points)

410
views
gateforumtestseries
engineeringmathematics
discretemathematics
graphtheory
graph
graphcoloring
+5
votes
4
answers
16
TIFR2016A2
Consider the graph shown below: The following experiment is performed using this graph. First, an edge $e =\{i,j\}$ of the graph is chosen uniformly at random from the set of 9 possibilities. Next, a common neighbour $k$ of $i$ and $j$ is chosen, again uniformly from the set of possibilities. (Note that ... $\frac{1}{6}$ $\frac{1}{4}$ $\frac{1}{3}$ $\frac{2}{3}$ $\frac{5}{6}$
asked
Dec 26, 2016
in
Others
by
jothee
Veteran
(
105k
points)

214
views
tifr2016
graph
probability
+1
vote
0
answers
17
DRDO2008
Adacency list is preferred over adjacency matrix when the graph is? A) planar B) Dense C) Clique D) none of these
asked
Jul 19, 2016
in
Algorithms
by
Anshul Shankar
Active
(
1.1k
points)

1.4k
views
madeeasytestseries
workbookquestion
drdo2008
graph
graphrepresentation
To see more, click for the
full list of questions
or
popular tags
.
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
ISRO CSE 2020 PAPER ANALYSE
BARC OCES/DGFS 2020
ISI CMI PDF by GATE Overflow
Calculus Important Points
Management Trainee Recruitment COAL INDIA 2020
Follow @csegate
Recent questions tagged graph
Recent Blog Comments
Has anyone else challenged the questions on...
@nkg_master9  For getting selected for the...
Nowhere it's mentioned.
@bond  Is it mentioned that you have to score at...
I think cutoff won't cross 85
50,737
questions
57,385
answers
198,547
comments
105,359
users