I am trying to solve:


Given $n, k$, find maximum $m$ such that there exists a graph on $n$ nodes, $m$ edges such that every edge is part of a minimal $k$-cycle.


I only care about the asymptotic value of $m$, and I don't care about log factors (so the answer will look like $m = \tilde O(n^c)$). This problem has applications to certain distance approximation algorithms in computer science.


Thanks!



How many edges can you put in a graph such that every edge belongs to a minimal $k$-cycle?
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](https://mathoverflow.net/questions/136920/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
arguments through.


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.


