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
Lists
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 in Graph Theory
Recent
Hot!
Most votes
Most answers
Most views
Featured
Previous GATE
Web Page
Connectivity,
Matching,
Coloring.
Recent
Hot!
Most votes
Most answers
Most views
Featured
Previous GATE
0
votes
1
answer
1
Discrete mathematics
asked
1 day
ago
in
Graph Theory
by
Deepalitrapti
Junior
(
663
points)

35
views
vertexcover
+1
vote
1
answer
2
virtual gate test
just explain the second statement
asked
3 days
ago
in
Graph Theory
by
Prince Sindhiya
Active
(
3.6k
points)

23
views
virtualgate
testseries
discretemathematics
0
votes
0
answers
3
virtual gate graph theory
i am getting 6 as answer
asked
3 days
ago
in
Graph Theory
by
Prince Sindhiya
Active
(
3.6k
points)

49
views
discretemathematics
graphtheory
+2
votes
2
answers
4
Degree of vertices
Consider an undirected graph with $n$ vertices, vertex $1$ has degree $1$,while each vertex $2,3,.............,n1$ has degree $4$.The degree of vertex $n$ is unknown. Which of the following statement must be true? $A)$ Vertex $n$ has degree ... connected $C)$ There is a path from vertex $1$ to vertex $n$ $D)$ Spanning tree will include edge connecting vertex $1$ and vertex $n$
asked
Oct 10
in
Graph Theory
by
Lakshman Patel RJIT
Loyal
(
9.6k
points)

51
views
discretemathematics
graphtheory
0
votes
1
answer
5
Bipartite graph
The number of ways to properly color (using just sufficient colors) a connected graph without any cycle using five colors, such a way that no two adjacent nodes have the same color?
asked
Oct 10
in
Graph Theory
by
Lakshman Patel RJIT
Loyal
(
9.6k
points)

45
views
discretemathematics
graphtheory
0
votes
1
answer
6
Complete Graph
Consider the following graph: Number of the Hamiltonian cycles starting and ending point at $ A$ is _______
asked
Oct 10
in
Graph Theory
by
Lakshman Patel RJIT
Loyal
(
9.6k
points)

64
views
engineeringmathematics
discretemathematics
graphtheory
+1
vote
0
answers
7
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
in
Graph Theory
by
Smishra95
Active
(
1.2k
points)

9
views
line
graph
+1
vote
0
answers
8
UGCNET CS 2017
An undirected graph G (V, E) contains n (n > 2) nodes named v1 , v2 ,...,vn. Two nodes vi and vj are connected if and only if 0 < │ i − j│ ≤2. Each edge (vi , vj ) is assigned a weight i+j. The cost of the minimum spanning tree of such a graph with 10 nodes is: A) 88 B)91 C)49 D)21
asked
Sep 28
in
Graph Theory
by
aditi19
Junior
(
863
points)

25
views
ugcnetnov2017iii
graphtheory
0
votes
0
answers
9
Can Null Graph be a valid Matching
Definition of valid matching says that if every vertex is incident with atmost one vertex then it is a matching but I have seen coaching material note which includes null graph as a matching.I am confused please help.
asked
Sep 28
in
Graph Theory
by
sripo
(
293
points)

8
views
graphtheory
discretemathematics
0
votes
0
answers
10
Is K2,4 planar graph
Is K 2,4 planar graph if yes can you please draw it?
asked
Sep 27
in
Graph Theory
by
sripo
(
293
points)

26
views
0
votes
0
answers
11
General query of Graph Theory
$1)$ Is there any general formula for maximum degree (if possible also minimum degree) of a vertex in a graph G? $2)$ Is there any relationship between indegree and outdegree of a graph?
asked
Sep 25
in
Graph Theory
by
srestha
Veteran
(
98.4k
points)

30
views
graphtheory
discretemathematics
general
0
votes
0
answers
12
State True or False
1) For undirected graph , number of subgraphs $2^{\binom{n}{2}}$ 2) For directed graph , number of subgraphs $\sum_{i=1}^{n}\binom{n}{i}2^{\binom{n}{2}}$ 3) For n elements, number of subsets $2^{n}$ 4) For n elements number of subrelations $n^{2}$ Are all these declaration correct?
asked
Sep 24
in
Graph Theory
by
srestha
Veteran
(
98.4k
points)

20
views
discretemathematics
0
votes
0
answers
13
Graph Theory
asked
Sep 21
in
Graph Theory
by
Anuj1995
(
285
points)

24
views
0
votes
0
answers
14
Graph Theory
asked
Sep 21
in
Graph Theory
by
Anuj1995
(
285
points)

30
views
+1
vote
0
answers
15
Graph Theory
asked
Sep 21
in
Graph Theory
by
Anuj1995
(
285
points)

22
views
0
votes
0
answers
16
Graph Theory
What is line graph?
asked
Sep 21
in
Graph Theory
by
Anuj1995
(
285
points)

22
views
0
votes
0
answers
17
GBDSATest 3Question 17
The line graph L(G) of a graph G(V, E) is a graph whose vertices are in 11 correspondence with the edges of G. Two vertices of L(G) being adjacent iff the corresponding edges of G are adjacent. Consider following graphs: Consider following statements: (i) L(A) is isomorphic to B. ... (iii) only (B) (ii) and (iii) only (C) (ii) and (iv) only (D) (ii), (iii) and (iv) only
asked
Sep 21
in
Graph Theory
by
Sandy Sharma
Junior
(
949
points)

43
views
discretemathematics
gatebook
0
votes
0
answers
18
GBDSATest 3Question 15Consider the graph shown below:
asked
Sep 21
in
Graph Theory
by
Sandy Sharma
Junior
(
949
points)

17
views
discretemathematics
gatebook
0
votes
0
answers
19
GBDSATest 3Question 18
Consider following statements about Cycle graph, Complete Bipartite graph and Complete graph. (i) Cycle graph Cn is subgraph of a complete graph Kn. (ii) Kn,n a subgraph of Km iff m ≤ 2n. (iii) Cn a subgraph of Kn,n iff n is even. Which of the above statements are true? (A) (i) and (ii) only (B) (ii) and (iii) only (C) (i) and (iii) only (D) (ii) only
asked
Sep 21
in
Graph Theory
by
Sandy Sharma
Junior
(
949
points)

17
views
discretemathematics
gatebook
0
votes
1
answer
20
Graph Coloring
A vertex colouring with four colours of a graph G = (V, E) is a mapping V → {R, G, B, Y }. So that any two adjacent vertices does not same colour. Consider the below graphs: The number of vertex colouring possible with 4 colours are _________.
asked
Sep 21
in
Graph Theory
by
srestha
Veteran
(
98.4k
points)

63
views
graphtheory
graphcoloring
0
votes
0
answers
21
Bipartite Graph
Which of the following complete bipartite graphs will have Hamiltonian cycle? $a)K_{3,3}$ $b)K_{2,4}$
asked
Sep 21
in
Graph Theory
by
srestha
Veteran
(
98.4k
points)

53
views
graphtheory
engineeringmathematics
0
votes
1
answer
22
Graph Theory
Every 3regular graph has a perfect matching? True or false?
asked
Sep 20
in
Graph Theory
by
Anuj1995
(
285
points)

89
views
0
votes
0
answers
23
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
Sep 18
in
Graph Theory
by
Sandy Sharma
Junior
(
949
points)

16
views
trees
discretemathematics
0
votes
1
answer
24
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.
asked
Sep 18
in
Graph Theory
by
Sandy Sharma
Junior
(
949
points)

24
views
trees
discretemathematics
0
votes
1
answer
25
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
asked
Sep 18
in
Graph Theory
by
Sandy Sharma
Junior
(
949
points)

13
views
discretemathematics
trees
0
votes
1
answer
26
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?
asked
Sep 18
in
Graph Theory
by
Devshree Dubey
Boss
(
13.6k
points)

21
views
graphtheory
0
votes
0
answers
27
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
Sep 18
in
Graph Theory
by
Sandy Sharma
Junior
(
949
points)

12
views
trees
discretemathematics
0
votes
1
answer
28
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
asked
Sep 18
in
Graph Theory
by
Sandy Sharma
Junior
(
949
points)

17
views
trees
0
votes
0
answers
29
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
Sep 14
in
Graph Theory
by
venkatesh456
(
9
points)

18
views
0
votes
1
answer
30
<2, 2, 2, 1, 1>degree sequence is NOT graphic for simple graphs?
asked
Sep 14
in
Graph Theory
by
venkatesh456
(
9
points)

32
views
Page:
1
2
3
4
5
6
...
23
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
Members at the site
aambazinga
Sawant Choudhary
Jayant
jat.gaurav
Shaik Masthan
Digvijay Pandey
Recent Posts
List of Available Exams
New Assignment on Network programming : P2P simulation
Theory of Computation  GO Classroom
Probability  GO Classroom
Daily Quiz
All categories
General Aptitude
1.4k
Engineering Mathematics
5.9k
Discrete Mathematics
4.1k
Mathematical Logic
1.7k
Set Theory & Algebra
1k
Combinatory
733
Graph Theory
667
Probability
840
Linear Algebra
564
Calculus
413
Digital Logic
2.3k
Programming & DS
4.3k
Algorithms
3.7k
Theory of Computation
4.6k
Compiler Design
1.7k
Operating System
3.4k
Databases
3.4k
CO & Architecture
2.9k
Computer Networks
3.4k
Non GATE
1.2k
Others
1.3k
Admissions
506
Exam Queries
482
Tier 1 Placement Questions
22
Job Queries
64
Projects
15
Follow @csegate
Gatecse
Recent questions in Graph Theory
Recent Blog Comments
Nice 2 know. You are welcome. :)
Hello @Arjun, I got books now...thanks for your...
You may contact FedEx local delivery office. It...
Yes you are right, it's showing this status from...
FedEx delivery is shown and as per that it is out...
40,903
questions
47,558
answers
146,288
comments
62,305
users