The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
GATE Overflow
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
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
Seld doubt DM
Consider a tree T with n vertices and (n – 1) edges. We define a term called cyclic cardinality of a tree (T) as the number of cycles created when any two vertices of T are joined by an edge. Given a tree with 10 vertices, what is the cyclic cardinality of this tree?
answered
13 hours
ago
in
Graph Theory
by
Shaik Masthan
Veteran
(
50.1k
points)

9
views
0
votes
1
answer
2
Tripartite Graph
The number of vertices,edges and colors required for proper coloring in Tripartite graph K<3,2,5> will be : 10 , 31 , 3 10 , 30 , 3 10 , 30 , 2 None
answered
19 hours
ago
in
Graph Theory
by
Priyadrasta Raut
(
117
points)

11
views
graphtheory
discretemathematics
madeeasytestseries
+1
vote
1
answer
3
Vertex Connectivity
The Vertex Connectivity of Graph is : 1 2 3 None
answered
19 hours
ago
in
Graph Theory
by
gate_dreams
(
297
points)

10
views
graphtheory
graphconnectivity
madeeasytestseries
0
votes
0
answers
4
Ace Academy Test series
If a 2 regular graph G has a perfect matching, then which of the following is NOT true? 1. G is a cycle graph 2. Chromatic number of G is 2 3. Every component of G is even cycle 4. G is a bipartite graph
asked
23 hours
ago
in
Graph Theory
by
Chaitrasj
Junior
(
799
points)

21
views
0
votes
0
answers
5
How to do such questions.
If $G$ is a bipartite graph with 6 vertices and 9 edges, then the chromatic number of $\overline G$ =
asked
1 day
ago
in
Graph Theory
by
`JEET
Active
(
3.2k
points)

35
views
0
votes
2
answers
6
Made Easy CBT 19 Discrete Maths
How to solve it(clear explanation please)
answered
1 day
ago
in
Graph Theory
by
Raja Rawal
(
457
points)

62
views
0
votes
0
answers
7
MADE_EASY
The Number of Labelled possible graph given below ? what I did was → we doesn’t remove any of the edge out of 4 = $\binom{4}{0}$ [Because a Graph is subgraph of itself] we can remove any of one edge out of 4 = $\binom{4}{1}$ we can remove any of the two edges out of 4 = $\binom{4}{2}$ similarly , $\binom{4}{3}$ , $\binom{4}{4 }$ then , add of the them
asked
1 day
ago
in
Graph Theory
by
Magma
Boss
(
12.7k
points)

26
views
madeeasytestseries
0
votes
0
answers
8
How this question can be done.
if G is a bipartite graph with 9 vertices and maximum number of edges, then vertex connectivity of G =
asked
1 day
ago
in
Graph Theory
by
`JEET
Active
(
3.2k
points)

10
views
0
votes
1
answer
9
ME CBT1
Can anyone explain how this is to be solved?
answered
2 days
ago
in
Graph Theory
by
Manas Mishra
Active
(
2.2k
points)

75
views
0
votes
0
answers
10
ACE Test series question on Chromatic number
asked
2 days
ago
in
Graph Theory
by
Shankar Kakde
(
249
points)

21
views
+23
votes
6
answers
11
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
3 days
ago
in
Graph Theory
by
Varun Belliappa
(
121
points)

1.4k
views
tifr2017
graphtheory
counting
+1
vote
1
answer
12
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 :/
answered
4 days
ago
in
Graph Theory
by
gmrishikumar
Junior
(
883
points)

153
views
graphtheory
discretemathematics
engineeringmathematics
0
votes
0
answers
13
TRUE/FALSE
State TRUE/FALSE Squaring all edges will NOT change the maximum spanning tree Squaring all edges will NOT change the minimum spanning tree Squaring all edges will NOT change the second maximum spanning tree Squaring all edges will NOT change the second ... tree Cubing all edges will change the second maximum spanning tree Cubing all edges will change the second minimum spanning tree
asked
5 days
ago
in
Graph Theory
by
Balaji Jegan
Active
(
4.6k
points)

18
views
+54
votes
6
answers
14
GATE201238
Let $G$ be a complete undirected graph on $6$ vertices. If vertices of $G$ are labeled, then the number of distinct cycles of length $4$ in $G$ is equal to $15$ $30$ $90$ $360$
answered
6 days
ago
in
Graph Theory
by
Hey
(
57
points)

8.2k
views
gate2012
graphtheory
normal
markstoall
counting
0
votes
0
answers
15
Graph_Self Doubt
Let G be a simple graph with 11 vertices . if degree of each vertex is atleast 3 and atmost 5 , then the number of edges in G should lie between I got 16 and 28
asked
Jan 8
in
Graph Theory
by
Magma
Boss
(
12.7k
points)

52
views
discretemathematics
0
votes
0
answers
16
rc test
Let G be a graph with 100 vertices numbered from 1 to 100. Two vertices i and j are adjacent if $\left  ij \right =8 $ or $\left  ij \right =12$ the number of connected components in G are a)8 b)4 c)12 d)25
asked
Jan 8
in
Graph Theory
by
Gate Fever
Active
(
4.4k
points)

20
views
0
votes
0
answers
17
rc test series
Assume G is a connected planar graph that has 12 vertices and 17 regions.all interior regions are bounded by a cycle of length 3(ie 3 edge).find the number of edges bounding the interior region?
asked
Jan 8
in
Graph Theory
by
Gate Fever
Active
(
4.4k
points)

38
views
0
votes
0
answers
18
rc test series
consider a simple graph G with k components.If each component has n1,n2,.....nk vertices,then the maximum number of edges in G is
asked
Jan 8
in
Graph Theory
by
Gate Fever
Active
(
4.4k
points)

23
views
0
votes
0
answers
19
rc test series
A graph is said to be 2 colorable if each vertex can be colored either red or blue and no two vertices of the same color are connected by an edge.If some graph is not 2 colorable then we can reduce it to become 2 colorable by removing some edges.we are given ... graph 2 colorable (ex ; k=0 if graph is already 2 colorable) the minimum value of k to reach the worst case is ______?
asked
Jan 8
in
Graph Theory
by
Gate Fever
Active
(
4.4k
points)

16
views
0
votes
0
answers
20
GATEBOOK2019 Grand Test Mathematics6
Consider the adjacency matrix of undirected graph $G$ ... where chromatic partition is defined as the number of integer (positive) partitions possible for the chromatic number of $G$? $1$ $2$ $3$ $4$
asked
Jan 7
in
Graph Theory
by
GATEBOOK
Boss
(
12.6k
points)

57
views
gb2019gtmaths
graphcoloring
0
votes
0
answers
21
Made_easy_test_series
The number of totally ordered sets compatible to the given POSET are ________.
asked
Jan 7
in
Graph Theory
by
Shivam Kasat
Active
(
1.6k
points)

55
views
discretemathematics
graphtheory
+26
votes
8
answers
22
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
Jan 7
in
Graph Theory
by
Rajesh Panwar
Junior
(
507
points)

2.8k
views
gate2009
graphtheory
graphcoloring
normal
0
votes
0
answers
23
SELF DOUBT PLANARITY
IS THERE ANY SHORT TIME SAVING METHOD TO DETERMINE GRAPH IS PLANNER OR NOT
asked
Jan 6
in
Graph Theory
by
eyeamgj
Loyal
(
6.6k
points)

23
views
0
votes
0
answers
24
self doubt
what is the chromatic number of null graph?
asked
Jan 6
in
Graph Theory
by
eyeamgj
Loyal
(
6.6k
points)

25
views
0
votes
0
answers
25
Self Doubt: What is the strategy to color a graph with minimum colors?
I know the fact that if a graph has a complete subgraph, say Kn, at least n will be the chromatic number. But what is the strategy for coloring vertices of a graph so that we need minimum colors? Many times it has happened that the order in which I color leads to more number of colors.
asked
Jan 6
in
Graph Theory
by
Pratik Gawali
Junior
(
827
points)

8
views
0
votes
0
answers
26
simple graph formula
why in this planar graph this theorem ,”sum of degrees of faces or regions is twice the number of edges” is not true as it should hold for all planar graphs?? Note: numbers denote region or face
asked
Jan 5
in
Graph Theory
by
BHASHKAR
(
19
points)

26
views
graphtheory
engineeringmathematics
discretemathematics
+8
votes
2
answers
27
ISI2015PCBC3
For a positive integer $n$, let $G = (V, E)$ be a graph, where $V = \text{{0,1}}^n$, i.e., $V$ is the set of vertices has one to one correspondence with the set of all $n$bit binary strings and $E = \{(u,v) \mid u, v$ belongs to $V, u$ and $v$ differ in exactly one bit position$\}$. Determine size of $E$ Show that $G$ is connected
answered
Jan 4
in
Graph Theory
by
HeadShot
Active
(
4.5k
points)

362
views
graphtheory
discretemathematics
isi2015
graphconnectivity
+47
votes
6
answers
28
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
Jan 4
in
Graph Theory
by
Prateek K
Active
(
1.9k
points)

6.1k
views
gate20141
graphtheory
numericalanswers
normal
graphconnectivity
0
votes
0
answers
29
gate zeal mock
The Number of Relations, Which are both Reflexive and Symmetric but not AntiSymmetric, on a set with 6 elements, are ____________? i got 32768 plz ceck
asked
Jan 2
in
Graph Theory
by
Prince Sindhiya
Loyal
(
6.1k
points)

31
views
zeal
mock
test
0
votes
0
answers
30
*** Test series
1.I is lattice, II is not lattice 2. I, II are not lattices 3.Both I, II are lattices 4. I is not lattice, II is lattice
asked
Jan 2
in
Graph Theory
by
piyushrawat01
(
31
points)

85
views
0
votes
0
answers
31
gate zeal mock
A simple graph is one in which there are no self loops and each pair of distinct vertices is connected by at most one edge. Let G be a simple graph on 8 vertices such that there is a vertex of degree 1, a vertex of degree 2, a vertex of degree 3, a vertex ... of degree 5, a vertex of degree 6 and a vertex of degree 7. Which of the following can be the degree of the last vertex ____ ?
asked
Jan 2
in
Graph Theory
by
Prince Sindhiya
Loyal
(
6.1k
points)

33
views
zeal
mock
test
0
votes
0
answers
32
Basic Doubt
Statement : "Every Euler Graph is a simple graph" Please comment whether it is true always or need not to be. ( My concern is whether multi edge or self loop is allowed in euler graph or not i. e nonsimple graph allowed or not )
asked
Jan 2
in
Graph Theory
by
HeadShot
Active
(
4.5k
points)

33
views
0
votes
0
answers
33
madeeasy
How to calculate closed region and open region from given dara.
asked
Jan 1
in
Graph Theory
by
mehul vaidya
Active
(
2.7k
points)

21
views
0
votes
0
answers
34
Eulerian Graph has to be connected?
A disconnected graph having even degree vertices can it be a euler graph?
[closed]
asked
Jan 1
in
Graph Theory
by
sripo
Active
(
1.3k
points)

50
views
graphtheory
eulergraph
graphconnectivity
madeeasytestseries
+15
votes
3
answers
35
GATE20074
Let $G$ be the nonplanar graph with the minimum possible number of edges. Then $G$ has 9 edges and 5 vertices 9 edges and 6 vertices 10 edges and 5 vertices 10 edges and 6 vertices
answered
Dec 31, 2018
in
Graph Theory
by
Badayayash
(
47
points)

2.4k
views
gate2007
graphtheory
normal
outofsyllabusnow
0
votes
0
answers
36
What to study & from where to study  Graph Theory for GATE 2019.
Are the following topics necessary/ apt to study for gate.(Bold items are explicitly mentioned in gate syllabus document) Connectivity Matching Coloring Cuts Covering Independent Sets Planar Graphs Isomorphism Walks, Trails, Paths, ... taking a lot of time. Can anyone please recommend a reliable and simple resource to go with.
asked
Dec 29, 2018
in
Graph Theory
by
Krishna Sai Vootla
(
23
points)

51
views
syllabus
engineeringmathematics
graphtheory
graphplanarity
graphisomorphism
vertexcover
0
votes
1
answer
37
ACE Test Series
answered
Dec 28, 2018
in
Graph Theory
by
Prince Sindhiya
Loyal
(
6.1k
points)

44
views
0
votes
0
answers
38
edge and vertex connectivity
how solve getting different answer???
asked
Dec 27, 2018
in
Graph Theory
by
altamash
(
417
points)

30
views
0
votes
0
answers
39
NTA NET Dec 2018 Q2
asked
Dec 25, 2018
in
Graph Theory
by
Sanjay Sharma
Veteran
(
50.2k
points)

56
views
graphtheorykcoloring
0
votes
0
answers
40
ME Test Series
asked
Dec 23, 2018
in
Graph Theory
by
Shadan Karim
Junior
(
939
points)

38
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
shgarg
Abhisek Tiwari 4
Kumar Anand
Ahwan
Kaushal Sanadhya
kd.....
Abbas
Simranyadav
newdreamz a1z0
tejas96
neel_mehta
Recent Posts
Decidability Slides
How to Revise?
AAI JE IT results out! Adv no 02/2018
Graph Theory Slides for GATECSE
Generating Function Useful Link
All categories
General Aptitude
1.5k
Engineering Mathematics
6.9k
Discrete Mathematics
4.8k
Mathematical Logic
1.9k
Set Theory & Algebra
1.3k
Combinatory
858
Graph Theory
775
Probability
966
Linear Algebra
682
Calculus
488
Digital Logic
2.7k
Programming & DS
4.8k
Algorithms
4.1k
Theory of Computation
5.2k
Compiler Design
2k
Operating System
3.9k
Databases
3.9k
CO & Architecture
3.4k
Computer Networks
3.9k
Non GATE
1.4k
Others
1.5k
Admissions
514
Exam Queries
525
Tier 1 Placement Questions
23
Job Queries
67
Projects
18
Follow @csegate
Gatecse
Recent questions and answers in Graph Theory
Recent Blog Comments
I have developed this weird addiction...
https://gateoverflow.in/exam/136/appliedcourse20...
1 fulllength test and revision...
46,766
questions
51,219
answers
176,464
comments
66,580
users