Here is a rough analysis to start things off. k=3 corresponds to a complete graph, and
k=4 to a complete bipartite graph with the vertex set split as evenly as possible. (I don't
see an easy proof of optimality, but I doubt one can cram more edges in. See Relationship between triangle free graphs and their minimum degree for why
I think this.) k=5 and 6 seem a little tricky, so in what follows assume k large enough to pull the
For any path outside of a given k cycle which connects two vertices of that cycle, that
path has to be as long as the longest of the two paths in the cycle that connect those two
vertices, otherwise the graph has girth less than k. Further, for k large (possibly k at least 5,
and certainly at least 10) two k cycles have at most two links between them, and at most one if
they share an edge. Here a link is an edge off of both cycles that shares a different vertex with each cycle.
Since the goal is to maximize the number of edges, I recommend partitioning the graph into disjoint
cycles and adding as many links as possible. I suspect this will give a good upper bound when k*k is at least
n. If l is n/k, this gives n + l^2 as a rough upper bound on the number of edges. The actual bound is
likely smaller as linking all pairs
of cycles may end up reducing the girth.