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.

1

$\begingroup$
$\endgroup$

As @bof points out, the star graph solves your problem (simple indeed):

It has $n-1$ edges for $n$ vertices.

connectedgraph on $n$ nodes must have at least $n-1$ edges, so the star graph is optimal. (I'm assuming that by "average" you mean the ordinary arithmetic average, i.e., add up the degrees of all the nodes and divide by the number of nodes.) $\endgroup$ – bof Nov 16 '18 at 5:40maximumdegree (instead of the average degree), that's a famous problem called thedegree-diameter problem. If you want to look that stuff up, you should learn the standard terminology. The "degree of separation" of two vertices is called theirdistance, the maximum degree of separation is called thediameterof the graph, a "fully connected" graph is called acompletegraph. $\endgroup$ – bof Nov 16 '18 at 5:45