• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Graph

 
Arjun Shastry
Ranch Hand
Posts: 1893
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
A graph has 50 edges.How many least number of vertices it can have?(no loops or multiple edges between two vertices please)
 
Nick George
Ranch Hand
Posts: 815
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
erhm... if an edge is defined to be the line between two vertecies, and the graph is continuous, wouldn't that make the only possible answers be 51 for a non-loop, and 50 for a loop?
 
Arjun Shastry
Ranch Hand
Posts: 1893
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Complete graph?
 
Bert Bates
author
Sheriff
Posts: 8898
5
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
could you define your terms more precisely ?
 
Barbara Norway
Ranch Hand
Posts: 150
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Sounds like maybe someone is working on some homework problems

Try this:
someone's homework answer

Or not....
 
Arjun Shastry
Ranch Hand
Posts: 1893
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Barbara Norway:
Sounds like maybe someone is working on some homework problems
Try this:
someone's homework answer
Or not....

No,I m not doing any homework problem. .
Graph has 50 edges.How many least vertices it can have?
This is the exact problem statement .I have taken this from
Applied combinatorics
 
Nick George
Ranch Hand
Posts: 815
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That being said, none of us (at least not me) understand what you're asking. Care to elucidate?
 
Jim Yingst
Wanderer
Sheriff
Posts: 18671
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I think the main problem here is with "no loops". It's not clear what's a loop. Is this a loop?

How about this? One loop? Two? Three? Zero?
 
Arjun Shastry
Ranch Hand
Posts: 1893
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thats circuit or cycle I think.AFAIK,loop means edge from one vertex to itself.
 
Arjun Shastry
Ranch Hand
Posts: 1893
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yes.
Cycle/Circuit
Loop
so if loop is allowed,then only one vertex will suffice.
Now I think the problem is easy.
I think I unnecessarily added that no loops statement.Not aware it will create confusion.

[ September 08, 2004: Message edited by: Arjun Shastry ]
[ September 08, 2004: Message edited by: Arjun Shastry ]
 
fred rosenberger
lowercase baba
Bartender
Pie
Posts: 12015
24
Chrome Java Linux
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
if you make a chart of # verticies vs. max. number of edges, then look at the delta...

1 0 0
2 1 1
3 3 2
4 6 3
5 10 4
6 15 5

the pattern is pretty clear. and it makes sense. if i have x verticies, each vertex will have x-1 edges coming into it, but that counts each edge twice. so i'd have (x * (x-1)) / 2 edges. simplify to (x^2 - x)/2

if i have x+1 verticies, i'd have ((x+1) * ((x+1)-1))/2, simplify to (x^2 + x)/ 2.

the difference between these is

anyway, if you continue this pattern, you can see that 11 are needed.

that's my quick take, but i'm probably wrong.

[ September 09, 2004: Message edited by: fred rosenberger ]
[ September 09, 2004: Message edited by: fred rosenberger ]
 
Arjun Shastry
Ranch Hand
Posts: 1893
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
.I too got the same answer.11 vertices.
So complete graph with 11 vertices.
Total degree = 11*10 = 110
Hence total edges = 110/2 = 55
If we take complete graph with 10 vertices,then we get 45 edges.
[ September 09, 2004: Message edited by: Arjun Shastry ]
 
Don't get me started about those stupid light bulbs.
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic