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
Exam Category
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.
Gatebook
+2
votes
149
views
Let A has n vertices. If Ā is connected graph then the maximum number of edges that A can have is
a) (n1)(n2)/2
b) n(n1)/2
c) n1
d) n
graphconnectivity
asked
Aug 19, 2016
in
Mathematical Logic
by
Sarvottam Patel
Active
(
1.2k
points)

149
views
Facebook
Google+
Twitter
answer
comment
I am getting option a , but by substitution , what is the standard way to solve it. I solve it for n=3,4 ,5 and got option a
think like ...
you have a grapg A with n vertices. excepts one vertex, all n1 vertices are making a complete graph with total
(n1)(n2)/2 edges. Now if we see complement of this graph then it would be connected right ( A' >star graph)??
And if we add any more edge in A, then it would make its complement disconnected ...
Note we are not told that A is also connected.. only A' is connected.
just give it think ..
Please
log in
or
register
to add a comment.
Please
log in
or
register
to answer this question.
1
Answer
+2
votes
Best answer
If $A^c$ is connected then minimum no. of edges in $A^c$ are n1
so maximum no. of edges in A= Total edges  minimum edges in $A^c$
= $_{2}^{n}\textrm{c}$  (n1)
=n(n1)/2 (n1)
=(n1)(n2)/2
option A)
answered
Aug 19, 2016
by
Sanket_
Loyal
(
4.3k
points)
selected
Aug 19, 2016
by
vijaycs
comment
option A is correct.
Please
log in
or
register
to add a comment.
← Prev. Qn. in Sub.
Next Qn. in Sub. →
← Prev.
Next →
Related questions
+1
vote
0
answers
1
graph theory
can we say a null graph is eulerian circuit and hamiltonian circuit?
asked
Jul 8
in
Mathematical Logic
by
akankshadewangan24
Loyal
(
3.7k
points)

66
views
graphtheory
graphconnectivity
0
votes
3
answers
2
[Discrete Maths] Graph Theory Rosen,Chromatic number
asked
Jun 13
in
Mathematical Logic
by
rahul sharma 5
Veteran
(
17.7k
points)

153
views
graphtheory
discretemathematics
graphconnectivity
graphmatching
+2
votes
2
answers
3
Discrete Maths Graph theory
What are the necessary and sufficient conditions for Euler path and Circuit in directed graph?
asked
Jun 13
in
Mathematical Logic
by
rahul sharma 5
Veteran
(
17.7k
points)

115
views
graphtheory
discretemathematics
graphconnectivity
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
Jobs @cvppindia
How to be productive?For all Members,GATE Aspirants, everybody associated with "GO Family"
How to Do preparation for Gate2018
How to write nice answers/questions in GO
Organizing NET Questions
All categories
General Aptitude
1.1k
Engineering Mathematics
4k
Discrete Mathematics
2.8k
Mathematical Logic
1k
Set Theory & Algebra
776
Combinatory
512
Graph Theory
462
Probability
516
Linear Algebra
402
Calculus
312
Digital Logic
1.7k
Programming & DS
3k
Algorithms
2.6k
Theory of Computation
3.2k
Compiler Design
1.2k
Operating System
2.3k
Databases
2.3k
CO & Architecture
2.1k
Computer Networks
2.4k
Non GATE
795
Others
1.2k
Admissions
244
Exam Queries
419
Tier 1 Placement Questions
16
Job Queries
39
Projects
4
Follow @csegate
Gatecse
Recent Blog Comments
Hi Guys, I think this is not correct. ISRO ...
NIELIT specifically mailed that they decided ...
is there any chances of changing the exam date??
ISRO and NIELIT Exam on the same day i.e 17th ...
greatly said @papesh sir
29,138
questions
36,958
answers
92,024
comments
34,802
users