Shortest path between two points on graph?

Question

A graph has 1000 vertices. Each vertex is connected to exactly 10 other vertices such that the whole graph is connected. If I choose two random vertices of the graph, what is the length of the shortest path between them?

Basically in a school, there's 1000 students; each has 10 friends. If I randomly choose two students, how 'close' to each other are they?

Answer 1

Let's suppose that these students go to Hypercube10 Highschool. In Mathematica, school = Graph[GraphData[{"Hypercube", 10}]] -- it's a graph with 1024 vertices and each vertex connects to 10 others.

We can get distances between 100000 random pairs of students.

data = Sort[Tally[Table[GraphDistance[school, RandomInteger[{1, 1024}], 
 RandomInteger[{1, 1024}]], {100000}]]]

{{0, 88}, {1, 968}, {2, 4392}, {3, 11658}, {4, 20845}, {5, 24618}, 
{6,20393}, {7, 11652}, {8, 4374}, {9, 923}, {10, 89}}

We'll want to throw out the 0's at the start. Totaling what's left

Total[Times @@ # & /@ Drop[data, 1]]/(100000 - data[[1, 2]]) // N 

We get 4.99747 ... quite close to 5. I'm going to guess 5 is a reasonably good answer. One way to consider this is the maximal spread from 1 student. There could be up to $10 \times 9 \times 9$ students at distance 4, but up to $10 \times 9 \times 9 \times 9 = 7290$ students at distance 5. But more than half the students are at distance 5.

If they went to Superclique Highschool instead, things would be different. There, students are friends in 100 ( $K_{10}$ - edge) cliques, with the cliques making $C_{100}$. There, the average distance seems to be 50.

We're assuming all students are connected. With 100 ( $K_{10}$ ) cliques, they wouldn't be.

There is a 13140 vertex degree-diameter graph with valence 10 and maximum distance 5 between students. There, the average distance is about 4.25.

So, it depends on how cliquish the high school is.