# Subgraphs where every pair of edges is in a short cycle

Erdös and Duke[1] showed that for a graph $$G$$ on $$n$$ vertices and $$\alpha n^2$$ edges, there is a subgraph $$G'$$ with $$c\alpha^3 n^2$$ edges with the property that every two edges of $$G'$$ lie together on a cycle of length at most six in $$G'$$, and , if two edges of $$G'$$ have a common vertex they are on a cycle of length four in $$G'$$. In a subsequent paper[2] together with Rödl, they proved that for a graph $$G$$ on $$n$$ vertices and $$n^{2-\beta}$$ edges, there is a subgraph $$G'$$ with $$c n^{2-5\beta}$$ edges with the property that every two edges of $$G'$$ lie together on a cycle of length at most six in $$G'$$, and, if two edges of $$G'$$ have a common vertex, they are on a cycle of length four in $$G'$$. The following questions remain unresolved:

# Problem

For any graph $$G$$ on $$n$$ vertices and $$n^{2-\beta}$$ edges, is it true that there is a subgraph $$G'$$ with $$c n^{2-3\beta}$$ edges with the property that every two edges of $$G'$$ lie together on a cycle of length at most six in $$G'$$, and, if two edges of $$G'$$ have a common vertex, they are on a cycle of length four in $$G'$$?

In [2] it was shown that "if two edges of $$G'$$ have a common vertex, they are on a cycle of length four in $$G'$$" is not required, then the answer to the above question is affirmative.

# Problem

For any graph $$G$$ on $$n$$ vertices and $$n^{2-\beta}$$ edges, is it true that there is a subgraph $$G'$$ with $$c n^{2-2\beta}$$ edges with the property that every two edges of $$G'$$ lie together on a cycle of length at most eight in $$G'$$?

In [2], it was shown that there is a subgraph $$G'$$ of the above graph $$G$$ with $$c n^{2-2\beta}$$ edges with the property that every two edges of $$G'$$ lie together on a cycle of length at most twelve in $$G'$$.

Bibliography
1 R. Duke and P. Erdös. Subgraphs in which each pair of edges lies in a short common cycle, Proceedings of the thirteenth Southeastern conference on combinatorics, graph theory and computing (Boca Raton, Fla., 1982), Congr. Numer. 35 (1982), 253-260.

2 R. Duke, P. Erdös and V. Rödl. More results on subgraphs with many short cycles. Proceedings of the fifteenth Southeastern conference on combinatorics, graph theory and computing (Baton Rouge, La., 1984), Congr. Numer. 43 (1984), 295-300.