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. For hardcopy of previous year questions please see
here
Recent questions and answers in Graph Theory
0
votes
1
answer
1
DSATest 3Question 9
Consider following statements: (i) Every simple graph has at least two vertices of the same degree. (ii) If u is a vertex of odd degree in a graph, then there exists a path from u to another vertex v of the graph where v also has odd degree. (iii) If there are exactly ... above statements are not true? (A) (i) and (ii) only (B) (iii) only (C) (ii) only (D) None of the above
answered
1 day
ago
in
Graph Theory
by
Shaik Masthan
Boss
(
25.9k
points)

6
views
discretemathematics
trees
0
votes
1
answer
2
DSATest 3Question 10
For which of the following scenarios does there exist a simple graph G = (V, E) satisfying the specified conditions? (A) It has 3 components 20 vertices and 16 edges. (B) It has 10 vertices, 38 edges, and more than one component. (C) It has 7 vertices, 10 edges, and more than two components. (D) It is connected and has 10 edges 5 vertices and fewer than 6 cycles.
answered
1 day
ago
in
Graph Theory
by
Shaik Masthan
Boss
(
25.9k
points)

7
views
trees
discretemathematics
0
votes
0
answers
3
DSATest 3Question 12
Let T = (V, E) be a tree and let d(v) be the degree of a vertex. Consider following statements: (i) P v∈V (2 − d(v)) = 2 (ii) If T has a vertex of degree m ≥ 2, then it has at least m vertices of degree 1. (iii) P v∈V (k − d(v)) = k, for k ≥ 2  k ∈ ... of the above statements is/are ture: (A) (i) only (B) (i), (ii) only (C) (ii) and (iii) only (D) (i), (ii) and (iii) only
asked
1 day
ago
in
Graph Theory
by
Sandy Sharma
Junior
(
837
points)

3
views
trees
discretemathematics
0
votes
1
answer
4
Graph Theory
Please help with the following: 1)How to determine if a graph is bipartite or not? 2)What is meant by ordered pair in case of a directed graph and unordered pair in case of an undirected graph?
answered
1 day
ago
in
Graph Theory
by
Shaik Masthan
Boss
(
25.9k
points)

12
views
graphtheory
0
votes
1
answer
5
DSATest 3Question 3
A quinpartite graph is a graph whose vertices can be partitioned into five groups such that no two vertices in same group are connected via some edge. The maximum number of edges in a quinpartite graph with 10 vertices, where cardinalities of those five sets are given as {2,3,2,1,2}, is: (A) 16 (B) 20 (C) 26 (D) 39
answered
1 day
ago
in
Graph Theory
by
Shaik Masthan
Boss
(
25.9k
points)

9
views
trees
0
votes
0
answers
6
DSATest 3Question 5
Consider following statements about tripartite graph, i.e. TPG, which contains three subsets of vertices of graph as A,B and C: (i) Minimum number of edges in a cycle in a TPG which passes through all three subsets of vertices is 6. (ii) A complete TPG can be colored with atmost 3 ... are true: (A) (i) only (B) (iii) only (C) (ii) and (iii) only (D) (i) and (ii) only
asked
1 day
ago
in
Graph Theory
by
Sandy Sharma
Junior
(
837
points)

2
views
trees
discretemathematics
0
votes
1
answer
7
<2, 2, 2, 1, 1>degree sequence is NOT graphic for simple graphs?
answered
5 days
ago
in
Graph Theory
by
Magma
Active
(
2.1k
points)

25
views
0
votes
0
answers
8
Let T = (V, E) be a tree, where V is the vertex set and E is the edge set. If E = 25, then V 
asked
5 days
ago
in
Graph Theory
by
venkatesh456
(
9
points)

14
views
0
votes
0
answers
9
nielit 2017
If G is an undirected planar graph on n vertices with e edges then A) e<=n B) e<=2n C) e<=3n D) None of the option plz explain it with solutions
asked
Sep 10
in
Graph Theory
by
RiteshSingh
(
249
points)

34
views
0
votes
1
answer
10
UGCNETjune2008ii4
The set of positive integers under the operation of ordinary multiplication is: (A) not a monoid (B) not a group (C) a group (D) an Abelian group
answered
Sep 10
in
Graph Theory
by
RiteshSingh
(
249
points)

176
views
ugcnetjune2008ii
0
votes
2
answers
11
ME test series.
How 14? I am not able to understand. Why not 30.
answered
Sep 6
in
Graph Theory
by
sakharam
Active
(
2k
points)

62
views
graphtheory
0
votes
0
answers
12
SELF DOUBT
https://gateoverflow.in/931/gate200340 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
in
Graph Theory
by
Deepanshu
Active
(
1.7k
points)

16
views
discretemathematics
0
votes
2
answers
13
kenneth H rosen 7th ed. Ex 10.3 q28
What is the sum of the entries in a row of the adjacency matrix for an undirected graph? For a directed graph?
answered
Sep 2
in
Graph Theory
by
abhishek kumar 34
(
39
points)

307
views
0
votes
1
answer
14
Isomorphic  NonIsomorphic Graphs
The Number of NonIsomorphic simple graphs upto 5 Nodes is _______
answered
Sep 2
in
Graph Theory
by
RashmiNitwane
(
11
points)

268
views
graphisomorphism
0
votes
0
answers
15
Doubt
What is converse of a graph?
asked
Sep 1
in
Graph Theory
by
aditi19
Junior
(
647
points)

11
views
graphtheory
0
votes
0
answers
16
NIELIT2017 STAsetc119
The function $f(x)=\frac{x^2 1}{x1}$ 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
in
Graph Theory
by
habedo007
Active
(
2k
points)

15
views
nielitjuly2017
continuity
differentiability
+19
votes
6
answers
17
GATE201028
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
answered
Aug 27
in
Graph Theory
by
shivamshukla
(
29
points)

3.7k
views
gate2010
graphtheory
degreeofgraph
+22
votes
6
answers
18
GATE20092
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$ $n1$ $n$
answered
Aug 26
in
Graph Theory
by
shivamshukla
(
29
points)

2.4k
views
gate2009
graphtheory
graphcoloring
normal
+1
vote
0
answers
19
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
in
Graph Theory
by
CJ147
(
43
points)

23
views
graphtheory
hamiltoncircuit
diractheorem
0
votes
1
answer
20
Graphs, kenneth rosen
How many nonisomorphic simple graphs are there with five vertices and three edges?
answered
Aug 25
in
Graph Theory
by
Mk Utkarsh
Boss
(
16.6k
points)

26
views
engineeringmathematics
discretemathematics
kennethrosen
graphtheory
+1
vote
1
answer
21
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.
answered
Aug 24
in
Graph Theory
by
arvin
Loyal
(
7.7k
points)

52
views
graphtheory
+14
votes
3
answers
22
GATE200535
How many distinct binary search trees can be created out of $4$ distinct keys? $5$ $14$ $24$ $42$
answered
Aug 24
in
Graph Theory
by
Mk Utkarsh
Boss
(
16.6k
points)

1.5k
views
gate2005
graphtheory
counting
normal
+30
votes
6
answers
23
GATE200336
How many perfect matching are there in a complete graph of $6$ vertices? $15$ $24$ $30$ $60$
answered
Aug 23
in
Graph Theory
by
Vijay Dulam
(
85
points)

3.5k
views
gate2003
graphtheory
graphmatching
normal
+1
vote
2
answers
24
Doubt
For a complete graph with 10 vertices, The number of spanning trees is at least_____?
answered
Aug 23
in
Graph Theory
by
arvin
Loyal
(
7.7k
points)

34
views
spanningtree
0
votes
2
answers
25
Proper edge coloring
What is the minimal number K such that there exists a proper edge coloring of the complete graph on 8 vertices with K colors? A) 28 B) 8 C) 7 D) 15
answered
Aug 20
in
Graph Theory
by
Rishav Kumar Singh
Active
(
4.2k
points)

70
views
graphtheory
edgecoloring
0
votes
1
answer
26
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
answered
Aug 17
in
Graph Theory
by
goxul
Active
(
2.3k
points)

27
views
+11
votes
3
answers
27
GATE200823
Which of the following statements is true for every planar graph on $n$ vertices? The graph is connected The graph is Eulerian The graph has a vertexcover of size at most $\frac{3n}{4}$ The graph has an independent set of size at least $\frac{n}{3}$
answered
Aug 16
in
Graph Theory
by
Pratik Gawali
(
169
points)

1.7k
views
gate2008
graphtheory
normal
graphplanarity
0
votes
1
answer
28
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?
answered
Aug 14
in
Graph Theory
by
MansiS
(
93
points)

46
views
probability
graphtheory
expectation
simplegraph
+1
vote
2
answers
29
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
answered
Aug 14
in
Graph Theory
by
Surajit13
(
11
points)

141
views
graphtheory
discretemathematics
+3
votes
2
answers
30
How many maximum cycles possible in any Complete graph? (Unlabelled nodes)
answered
Aug 14
in
Graph Theory
by
K_Nishant
(
75
points)

238
views
graphtheory
cycle
+4
votes
2
answers
31
Number of Hamiltonian cycles in a complete graph
answered
Aug 13
in
Graph Theory
by
K_Nishant
(
75
points)

361
views
graphtheory
cycle
+1
vote
4
answers
32
Isomorphic graphs
Ans is a) Can anyone plz explain how G1 and G2 are isomorphic?
answered
Aug 9
in
Graph Theory
by
JPranavc
(
281
points)

337
views
+43
votes
5
answers
33
GATE2014151
Consider an undirected graph $G$ where selfloops 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 $ac \leq 1$ and $bd \leq 1$. The number of edges in this graph is______.
answered
Aug 9
in
Graph Theory
by
sutanay3
Active
(
2.6k
points)

4.9k
views
gate20141
graphtheory
numericalanswers
normal
graphconnectivity
+3
votes
2
answers
34
Nonisomorphic graphs
How many nonisomorphic simple graph are there with N vertices, where N = 4 ?
answered
Aug 9
in
Graph Theory
by
K_Nishant
(
75
points)

1.9k
views
0
votes
1
answer
35
Ace material
If a graph with 10 vertices having each vertex having degree >=5 find graph connected or disconnected
answered
Aug 8
in
Graph Theory
by
sourav.
Boss
(
16.1k
points)

18
views
0
votes
1
answer
36
ACE Bits and bYtes
Minimum no of edges necessary in a simple graph with 10 vertices to ensure connectivity is_______.
answered
Aug 8
in
Graph Theory
by
gparamesh.1997
(
17
points)

84
views
graphtheory
graphconnectivity
0
votes
0
answers
37
Graph Theory
[closed]
asked
Aug 6
in
Graph Theory
by
BharathiCH
(
195
points)

15
views
0
votes
0
answers
38
Show that T is a maximum spanning tree for G
asked
Jul 24
in
Graph Theory
by
abram19000
(
7
points)

28
views
graphtheory
graphalgorithms
+1
vote
1
answer
39
ACE Bits And Bytes
Number of perfect matching in Wn (n>=4 and n is even) _________.
answered
Jul 24
in
Graph Theory
by
Shaik Masthan
Boss
(
25.9k
points)

40
views
graphtheory
graphmatching
gate2019
0
votes
1
answer
40
Graphs
answered
Jul 20
in
Graph Theory
by
Shaik Masthan
Boss
(
25.9k
points)

46
views
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
srestha
Sasta_yoda
Recent Posts
kvs pgt
Algorithms GO Classroom
Programming and DS GO Classroom
Discrete Mathematics GO Classroom
Digital Logic GO Classroom
All categories
General Aptitude
1.4k
Engineering Mathematics
5.6k
Discrete Mathematics
3.9k
Mathematical Logic
1.6k
Set Theory & Algebra
986
Combinatory
691
Graph Theory
640
Probability
698
Linear Algebra
550
Calculus
403
Digital Logic
2.2k
Programming & DS
4.1k
Algorithms
3.6k
Theory of Computation
4.4k
Compiler Design
1.7k
Operating System
3.2k
Databases
3.2k
CO & Architecture
2.8k
Computer Networks
3.2k
Non GATE
1.1k
Others
1.5k
Admissions
503
Exam Queries
470
Tier 1 Placement Questions
21
Job Queries
61
Projects
13
Follow @csegate
Gatecse
Recent questions and answers in Graph Theory
Recent Blog Comments
Last week was break. Probability started this...
@Ahwan Please share ur interview experience
@Barney Full course for Gate17 in my final year.
Gr8
39,481
questions
46,655
answers
139,565
comments
57,349
users