# How many edges can you put in a graph such that every edge belongs to a minimal $k$-cycle?

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!

• What do you mean by a minimal $k$-cycle? – Seva Feb 11 '14 at 9:13
• I think a graph of girth k on n vertices is wanted. Also, for large k, any two such cycles have at most two links between them. Here a link is an edge off of both cycles that has a vertex on each cycle. – The Masked Avenger Feb 11 '14 at 16:33
• By minimal $k$-cycle, I mean that no proper subset of the $k$ vertices forms a cycle. Another way of phrasing this question is "every edge belongs to a cycle, and the graph has girth $k$." – GMB Feb 11 '14 at 21:17
• @GMB These are not equivalent definitions! One can construct a graph, such that every edge is in a chordless k-cycle (no proper subset of these $k$ vertices form a cycle) but the graph contains a triangle. – Daniel Soltész Feb 11 '14 at 21:51
• I think it is also intended that for every edge, that edge belongs to a cycle, and the minimum of the girths of all cycles containing that edge is k, and this holds for all edges. – The Masked Avenger Feb 11 '14 at 23:14

• If by minimal cycles the OP means just induced ones, then the $k=4$ case has a better example, namely $K_{2,2,2,\dots,2}$ (or $K_{2,2,\dots,2,3}$ if $n$ is odd). OTOH, if a graph of girth $k$ is needed, then the optimality of a complete bipartite graph is confirmed by Turan's theorem. – Ilya Bogdanov Sep 17 '16 at 17:45