[ Post a Response | Puzzles Forum ]
Posted by Moby Dick
on 7/8/2009, 9:44 pm, in reply to "Might Not Be Possible?"
The question is: for a graph of 14 vertices, what is the minimum number of edges needed to give a diameter of 2?
The nearest expression I have found is here. The expression given is:
(5 * n) / 2 - 7
For 14 vertices, this would imply 28 edges - which ought be doable - since each round contains 7 games - each of which represents an edge on the graph.
However:
1. The expression is only proven for n > 37 (and n even)
2. The extremal graph that achieves this need not necessarily have 4 edges connected to each vertex
Message Thread:
« Back to thread