Proof. Subdivide the edges. i.e., replace the edges with paths of length \(k/r\).

Proof. Exchange each \(B\times C\) edge for a path of length \(k-2\), i.e., subdivide those edges.

It is clear that triangles get converted into \(k\)-cycles. To see the other direction it is helpful to partition the vertex set into \(A,B,C, D_1,D_2,\ldots, D_{k-3}\) where \(D_i\) is the vertices which are \(i\) steps along a \(B\to C\) path.

Observe that if we delete any of these parts the graph becomes bipartite, and then we could certainly not find a \(k\)-cycle in it. Hence every \(k\)-cycle must actually use one of the \(B \times C\) path / edge things and thus actually corresponds to a triangle in the original graph.

Proof. Do a 2 step BFS out of every vertex. For each pair \(u,v\) make a list of the paths of length \(2\) between \(u,v\).

Then itterate over \(u,v\) and itterate over pairs of paths of length \(2\) between \(u, v\): each of these is a four-cycle.

Proof. Let \(L\) be the set of low-degree vertices, i.e., vertices with degree smaller than \(m^{1/3}\). Let \(H\) be the high degree vertices.

We break it into a few cases:

• 2-paths wtih an L at the middle
• 2-paths consisting solely of H vertices
• “LHH” 2-paths. these ones are more tricky. But we only have to list half of them. So they direct the graph in an interesting way.

Proof. Itterate over edges, if the edge has a low-degree endpoint itterate over that endpoint’s neighbors. Time \(O(m^{4/3})\)

Proof. At most \(m^{4/3}\) pairs of high deg vertices. Let \(G'\) be the graph where we have removed low degree vertices. This can be computed in time \(O(m)\). Now we do a 2-step BFS out of each vertex in \(G'\). You have to pay for the first 2-path you list between each pair of high degree vertices. After the first one though the rest get charged to \(4\)-cycles.

Proof. \(\lambda_1(G) \ge d^{4}\). The number of walks of length 4 is \(tr(A^{4}) \ge \lambda_1(G)\). The number of 4-walks is equal to number of squares plus the number of 2-paths (degenerate C4s):

The number of \(2\)-paths is simply: \[\sum_{uv} codeg(u,v) \le O(n^{2} + \# C_4).\]

In summary:

\[\# C_4 + \# P_2 \ge d^{4}\] so

\[\# C_4 \ge \Omega(d^{4}-n^{2}).\]

Proof.

Start by selecting each high-degree vertex to join \(A\) with probability \(1/2\). This kills \(3/4\) of the \(L\to H\to H\) paths on average. Now bucket the nodes based on \(\left\lfloor \log_2 \cdot \right\rfloor\) in arrows from L and out arrows to B.

Proof. Combine the lemmas.

Proof. Combine the lemmas.

Proof.

for (b,c) in BxC cap Edges :
  for a in N[b] cap A:
    insert b into N[a,c]
    if |N[a,c]| == 2:
      insert c into Q[a,d] for all d in N[c] cap D
  for d in N[c] cap D:
    insert c into N[b,d]

    similar condition to above to add paths to P[a,d]

for (b,c) in BxC cap Edges:
  Sa = {a in N[b] cap A : |N[a,c]|==1}
  Sd = {d in N[c] cap D : |N[b,d]|==1}
  for (a,d) in Sa x Sd:
    insert (b,c) into R[a,d]

I think there is a simpler way of phrasing this that still works:

List all 2-paths by doing a 2-step BFS out of every vertex.
While listing the 2-paths for each vertex create a list of their "2-step neighbors"
for a in A:
  for c in 2-step neighbors of a:
    for d in D neighbors of c:
      if there are multiple a -> c 2-paths:
        mark c as an (a,d) dead-fish
      elif there is a unique b for which a->b->c:
        mark (b,c) as an (a,d) irreplacable-path

This should be fine because we have the OP lemma that we can afford to list P2’s.

claim: this code is \(O(n^2 + \text{ table size})\). proof: Basically on most lines of the code we are inserting into the table.

Proof. We do cases on what type of paths the C6 is composed of.

• Case 3: RR

for a in A, d in D:
  for (b1,c1) in R[a,d], (b2,c2) in R[a,d]:
    if (b1,c1) != (b2,c2):
      output C6: a,b1,c1,d,c2,b2

• Case 4: P/Q R.

similar to case 3

• Case 1: PQ

for a in A, d in D:
  for b1 in P[a,d], c2 in Q[a,d]:
    for b2 in N[b1,d], c1 in N[a,c2]:
      if b1 != b2 and c1 != c2:
        output C6: a b1 b2 d c2 c1

The reason this works is because the neighbor sets are size at least \(2\) so when we do “choose 2” it doesn’t become 0. I.e., for \(n\ge 2\) we have \[\binom{n}{2}\ge \frac{n^2}{4}.\] Or at least its this kind of vibe.

• Case 2: similar to case 1

Proof. First we analyze the PQR stuff.

PQR: Suppose that \(|P_{a,d}|=x\ge 2\). Then you get at least \(\binom{x}{2}\ge x-1\) hexagons. So we get \[\sum_{a,d}|P_{a,d}|\le O(n^{2}+C_6).\]

Remains to show that listing the common neighbors of every pair of vertices is fine. The argument is based on this key fact:

If \(a\in A\) satisfies \(\sum_{c\in C} |N_{a,c}|\ge 100n+k\) then there are at least \(k\) C6’s for which \(a\) is the only \(A\) vertex in the C6.

Let \(G_a\) (basically) be the 2-step BFS tree out of \(a\). We form \(G_a'\) as follows: itteratively delete vertices while there is a vertex of degree at most \(2\). This deletes at most \(2\) edges per vertex, for a total of at most \(2n\) edges. Hence, \(|E(G_a')|\ge 98n+k\). Now we can greedily find a C6.

I was initially a bit confused by this. Because I thought the idea with the color-coding is that we were only going to list the C6’s spanning ABCD. But this isn’t part of the algorithm, this is part of the analysis.

So anyways, this lets us prove:

\[\sum_{c\in C} |N_{a,c}|-100n\] is a lower bound on the number of \(C_6\)’s for which \(a\) is the only \(A\) vertex in the \(C_6\).

Hence, \[C_6 \ge \sum_{a\in A}\sum_{c\in C} (|N_{a,c}|-100n).\] Thus, \[\sum_{a,c} |N_{a,c}| \le O(n^{2}+C_6).\]

lovely!