First time here? Checkout the
FAQ
!
x
Use the google search bar on side panel. It searches through all previous GATE/other questions. For hardcopy of previous year questions please see
here
Login
Remember
Facebook Login
Register
GATE Overflow
Grant Access
All Activity
Questions
Unanswered
Tags
Categories
Users
Ask a Question
Lists
Previous
Blogs
New Blog
Exams
Recent
Hot!
Most votes
Most answers
Most views
Featured
Previous GATE
Ask a Question
Web Page
Connectivity,
Matching,
Coloring.
Recent questions in Graph Theory
0
votes
1
answer
1
GATEBOOK-2019-OS1-15
Consider the grammar $S\rightarrow ACB \mid cbB \mid Ba$ $A\rightarrow da \mid BC$ $B\rightarrow g \mid \epsilon $ $C \rightarrow h \mid \epsilon $ FIRST (A) will be $\{d, g, h, \}$ $\{d, g, h, a \}$ $\{d, h, g, b, \}$ $\{g, h, a, \}$
asked
Dec 30, 2018
in
Graph Theory
by
GATEBOOK
Loyal
(
7.7k
points)
0
views
gb2019-dm1
0
votes
0
answers
2
SELF DOUBT
https://gateoverflow.in/931/gate2003-40 IN THE SOLUTION AT LAST 3 STATEMENTS 0≤−6. which is definitely inconsistent. Hence, answer = option (D) WE PUT 6 HERE THEN IF WE DONT HAVE VALUES MEANS FILL IN THE BLANKS THEN.............. IS THERE ANY METHOD TO SOLVE THIS OR ANYTHING ??????
asked
Sep 2, 2018
in
Graph Theory
by
Deepanshu
Active
(
1.3k
points)
15
views
discrete-mathematics
0
votes
0
answers
3
Doubt
What is converse of a graph?
asked
Sep 1, 2018
in
Graph Theory
by
aditi19
Junior
(
549
points)
10
views
graph-theory
0
votes
0
answers
4
NIELIT2017 STA-set-c-119
The function $f(x)=\frac{x^2 -1}{x-1}$ at $x=1$ is: (A) Continuous and Differentiable (B) Continuous but not Differentiable (C) Differentiable but not Continuous (D) Neither Continuous nor Differentiable
asked
Aug 31, 2018
in
Graph Theory
by
habedo007
Active
(
2k
points)
12
views
nielit-july-2017
continuity
differentiability
+1
vote
0
answers
5
Kenneth Rosen Discrete Mathematics
DIRAC’S THEOREM: If G is a simple graph with n vertices with n ≥ 3 such that the degree of every vertex in G is at least n/2, then G has a Hamilton circuit. The below graph does not follow the above rule but still have a Hamilton circuit.
asked
Aug 25, 2018
in
Graph Theory
by
CJ147
(
39
points)
21
views
graph-theory
hamilton-circuit
dirac-theorem
+1
vote
1
answer
6
Number of Eulerian Graphs
Find the number of connected Eulerian graphs with 6 unlabelled vertices. Draw each of them. Note: I'm looking for a fast procedure don't comment just the numerical answer.
asked
Aug 24, 2018
in
Graph Theory
by
Mk Utkarsh
Boss
(
15.7k
points)
51
views
graph-theory
+1
vote
2
answers
7
Doubt
For a complete graph with 10 vertices, The number of spanning trees is at least_____?
asked
Aug 23, 2018
in
Graph Theory
by
Rishav Kumar Singh
Active
(
4.1k
points)
31
views
spanning-tree
0
votes
1
answer
8
Graph theory
In tree for every pair of vertices u!=v in G their is exactly 1 path from u to v .Please help me to prove this
asked
Aug 17, 2018
in
Graph Theory
by
Shivangi Parashar 2
(
63
points)
27
views
+1
vote
2
answers
9
Graph theory Modified
What is the maximum integer value m such that every simple connected graph with r vertices and r+2 edges contains at least m different spanning trees ? 1)1 2)4 3)8 4)m
asked
Aug 13, 2018
in
Graph Theory
by
srestha
Veteran
(
94k
points)
140
views
graph-theory
discrete-mathematics
0
votes
1
answer
10
Ace material
If a graph with 10 vertices having each vertex having degree >=5 find graph connected or disconnected
asked
Aug 8, 2018
in
Graph Theory
by
gparamesh.1997
(
17
points)
18
views
0
votes
0
answers
11
Graph Theory
[closed]
asked
Aug 6, 2018
in
Graph Theory
by
BharathiCH
(
177
points)
15
views
0
votes
0
answers
12
Show that T is a maximum spanning tree for G
asked
Jul 24, 2018
in
Graph Theory
by
abram19000
(
7
points)
28
views
graph-theory
graph-algorithms
0
votes
1
answer
13
ACE Bits and bYtes
Minimum no of edges necessary in a simple graph with 10 vertices to ensure connectivity is_______.
asked
Jul 24, 2018
in
Graph Theory
by
abhishek1995_cse
(
35
points)
76
views
graph-theory
graph-connectivity
+1
vote
1
answer
14
ACE Bits And Bytes
Number of perfect matching in Wn (n>=4 and n is even) _________.
asked
Jul 24, 2018
in
Graph Theory
by
abhishek1995_cse
(
35
points)
36
views
graph-theory
graph-matching
gate-2019
0
votes
0
answers
15
SELF DOUBT
https://gateoverflow.in/510/gate1991-01-xv IN THIS QUESTION I AM SOLVING LIKE THIS WE HAVE K COMPONENTS 1,2,3,.................K EACH OF WHICH HAVE N1,N2,N3,.................NK VERTICES SO TOTAL NUMBER OF EDGES ARE N1(N1-1)/2 +N2(N2-1)/2...................NK(NK-1)/2 SO AT SOMEWHERE IN STEPS I REACHED TO 1/2((-N)+N12+N22.......NK2)) NOT GETTING FURTHER FROM HERE ..................
asked
Jul 19, 2018
in
Graph Theory
by
eyeamgj
Active
(
4.1k
points)
22
views
0
votes
1
answer
16
Graphs
asked
Jul 18, 2018
in
Graph Theory
by
HeadShot
Junior
(
857
points)
46
views
0
votes
1
answer
17
Graphs
I think ans is option C , But will anybody explain the notation used in option D ?
asked
Jul 18, 2018
in
Graph Theory
by
HeadShot
Junior
(
857
points)
34
views
0
votes
1
answer
18
me test
A simple graph with n vertices is constructed by randomly and independently placing an edge between every two vertices with probability p. What is the expected no. of nodes with degree 2?
asked
Jul 17, 2018
in
Graph Theory
by
ronin_codex
(
7
points)
44
views
probability
graph-theory
expectation
simple-graph
+1
vote
0
answers
19
Graph Theory
asked
Jul 15, 2018
in
Graph Theory
by
Bhagyashree Mukherje
Active
(
1.2k
points)
54
views
testbook-test-series
0
votes
0
answers
20
graph theory
10.A graph G has any two vertices connected by exactly one path. Find the Number of ways we can properly colour G it we are provided with 10 colours.
asked
Jul 14, 2018
in
Graph Theory
by
poojasharma123
(
85
points)
77
views
graph-theory
0
votes
0
answers
21
UGC NET JULY 2018 Q81
asked
Jul 10, 2018
in
Graph Theory
by
Sanjay Sharma
Boss
(
49k
points)
57
views
+1
vote
1
answer
22
SELF DOUBT PREFIX
WE CAN USE STACK TO EVALUATE PREFIX EXPRESSION .THIS STATEMENT IS TRUE OR FALSE IF THEN HOW?? EXPRESSION IS + - * 2 3 5 / ^ 2 3 4
asked
Jul 8, 2018
in
Graph Theory
by
eyeamgj
Active
(
4.1k
points)
42
views
0
votes
0
answers
23
kenneth rosen
Given n+1 symbols x1,x2,...,xn,xn+1 appearing 1, f1,f2,...,fn times in a symbol string, respectively, where fj is the jth Fibonacci number, what is the maximum number of bits used to encode a symbol when all possible tie-breaking selections are considered at each stage of the Huffman ... of symbols should be n+1 i.e 7 (in this case ansewr is 8)or n i.e 6( in this case answer is 6)???
[closed]
asked
Jul 8, 2018
in
Graph Theory
by
eyeamgj
Active
(
4.1k
points)
54
views
0
votes
1
answer
24
SELF DOUBT DM ROSEN
Find the least number of comparisons needed to sort ﬁve element. I AM GETTING 7 AS (LOG 5!) =7........
asked
Jul 8, 2018
in
Graph Theory
by
eyeamgj
Active
(
4.1k
points)
32
views
0
votes
1
answer
25
rosen
asked
Jul 7, 2018
in
Graph Theory
by
eyeamgj
Active
(
4.1k
points)
51
views
0
votes
0
answers
26
Gate 2018 Qn. 43
Let G be a graph with 100! vertices, with each vertex labelled by a distinct permutation of the numbers 1,2,…,100. There is an edge between vertices and if and only if the label of can be obtained by swapping two adjacent numbers in the label of . Let denote the degree of a vertex in G, and denote the number of connected components in G. Then, y + 10z = _____.
asked
Jul 6, 2018
in
Graph Theory
by
Optimus Prime
(
425
points)
39
views
graph-theory
+1
vote
1
answer
27
self doubt
in a rooted tree if we are asked to find the level of root then it should be 0 or 1 or question depending ??
asked
Jul 5, 2018
in
Graph Theory
by
eyeamgj
Active
(
4.1k
points)
30
views
0
votes
0
answers
28
How to find even or odd cylce in a graph
asked
Jun 30, 2018
in
Graph Theory
by
ejaz
(
217
points)
28
views
graph-coloring
0
votes
2
answers
29
self doubt
Is it necessary that euler graph should always be simple graph?
asked
Jun 27, 2018
in
Graph Theory
by
Vegeta
(
227
points)
52
views
discrete-mathematics
graph-theory
0
votes
0
answers
30
Kenneth rosen
How many non-isomorphic directed graphs are there with $n$ vertices when $n$ is $2$ $3$ $4$
asked
Jun 18, 2018
in
Graph Theory
by
swati96
(
37
points)
34
views
engineering-mathematics
discrete-mathematics
kenneth-rosen
graph-theory
Page:
1
2
3
4
5
6
...
22
next »
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
No.of Favorite questions in GO per user
ISRO interview experience
List of useful tables for Gate Computer Science
IOCL interview preparation and experience
IITD interview
Follow @csegate
Gatecse
Recent questions in Graph Theory
Recent Blog Comments
@MiNiPanda Thank you !!Sorry I mentioned ur name...
Arjun Sir by creating such an amazing platform of...
@Sagar Yes i do remember sagar. Thanks for your...
Thank you everyone :)
@Arjun Sir Wish you happy teachers day
...