Consider an algorithm for generating an undirected graph using random numbers, whose pseudocode is given below.
let be an undirected graph with and ;
for to do
begin
let be a new vertex;
let and be distinct vertices randomly selected from ;
let be an undirected graph with and
;
end
Note that for any pair of distinct vertices , the selection probability is positive. Obviously, any graph constructed by this algorithm is connected, has vertices, and does not contain a self-loop or a multi-edge. In the following, we use to denote .
For a graph , denotes the degree of a vertex (i.e., the number of edges connecting to ), and denotes the length (i.e., the number of edges) of the shortest path (i.e., the path consisting of the minimum number of edges) between two distinct vertices and in . Note that and are positive integers depending on randomly selected vertices in the algorithm.
In the following, is an even number greater than or equal to 4. Let be the set of all possible undirected graphs generated by this algorithm. For example, for any ,
and hold because always holds and always holds for any vertex .
Derive the following values. Note that the values may be given as mathematical expressions of .