Win a copy of Mesos in Action this week in the Cloud/Virtualizaton forum!

# Graph

Arjun Shastry
Ranch Hand
Posts: 1898
1
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
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: 1898
1
Complete graph?

Bert Bates
author
Sheriff
Posts: 8898
5
could you define your terms more precisely ?

Barbara Norway
Ranch Hand
Posts: 150
Sounds like maybe someone is working on some homework problems

Try this:

Or not....

Arjun Shastry
Ranch Hand
Posts: 1898
1
Originally posted by Barbara Norway:
Sounds like maybe someone is working on some homework problems
Try this:
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
That being said, none of us (at least not me) understand what you're asking. Care to elucidate?

Jim Yingst
Wanderer
Sheriff
Posts: 18671
I think the main problem here is with "no loops". It's not clear what's a loop. Is this a loop?

Arjun Shastry
Ranch Hand
Posts: 1898
1
Thats circuit or cycle I think.AFAIK,loop means edge from one vertex to itself.

Arjun Shastry
Ranch Hand
Posts: 1898
1
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
Posts: 12125
30
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: 1898
1
.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 ]