User inputs: number of nodes (n) and number of links (k).
Objective: create an undirected (n,k) graph without multi-edges and without self loops that exhibits the maximum standard deviation in its degree distribution. In other words, create a graph in which the nodes have degrees with the highest variance.
My greedy algorithm: assign the first node n-1 (maximum possible number) links. Assign the second node n-2 links. Assigned the third node n-3 links... And so on. Till the total number of links in the graph reaches k.
Seeking help on: I'm unable to prove that this greedy algorithm guarantees the maximum standard deviation in the degree distribution of the graph.
Note: The following has been confirmed, via code, for all $k\le n\le 30$. A proof of this claim is requested by Aman Kabra for an acceptable answer.
Your greedy algorithm is optimal, but you need to check two cases. The first case is $f(n,k)$ and the second case is $f(n,c-k)$, where $c=\frac{n(n-1)}{2}$, the number of edges in a complete graph on $n$ vertices. The complement of the graph from the second case has $k$ edges, and one or both of these cases will provide a graph of maximal variance.