Graph

[Arjun Shastry]

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]

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]

Complete graph?

[Bert Bates]

could you define your terms more precisely ?

[Barbara Norway]

Sounds like maybe someone is working on some homework problems

Try this:
someone's homework answer

Or not....

[Arjun Shastry]

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]

That being said, none of us (at least not me) understand what you're asking. Care to elucidate?

[Jim Yingst]

I think the main problem here is with "no loops". It's not clear what's a loop. Is this a loop?

    x
   /|
  / |
 /  |
x   |
 \  |
  \ | 
   \|
    x

How about this? One loop? Two? Three? Zero?

    x
   / \
  /   \
 /     \
x-------x
 \     /
  \   / 
   \ /
    x

[Arjun Shastry]

Thats circuit or cycle I think.AFAIK,loop means edge from one vertex to itself.

[Arjun Shastry]

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]

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

(x^2 + x) - ( x^2 - x)              2x
---------------------        =      ---      = x
          2                          2

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]

.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 ]