Is there a simple way to construct such a graph? For example a fully connected graph obviously has degree of separation between every vertex of 1 but has maximal total degree. If we only wanted to minimise the total degree then I think the answer would be a star graph. But I want the average degree to be smallest rather than just relying on a single high degree vertex to be the common neighbour for all vertices. I can sort of see an algorithm starting with a cycle5 graph and adding nodes until the degree of separation between each pair of nodes is <= 2, but not sure if this would be optimal.