Let $G$ be a tripartite graph: its vertices are partitioned into three sets $A$, $B$, and $C$, and all edges go from one set to another, like in the graph used to prove 3SUM-hardness of triangle finding. Consider the following algorithm for finding triangles in such graphs:
While the graph is not empty, choose an edge $uv$ such that the number of neighbors $w$ of $v$ that are in the other set from $u$ is minimized. (That is, if $u$ is in $A$ and $v$ is in $B$, we only count neighbors $w$ of $v$ that are in $C$, and we choose $uv$ to minimize this count.) For each such $w$, test whether $uvw$ is a triangle, and if so report it. Then delete edge $uv$ from the graph.
Prove that the number of pairs of edges tested by this algorithm is $O(md)$ for graphs with m edges and degeneracy $d$.
Describe the data structures needed to perform this algorithm in constant time per pair of edges that it tests. (You may use hash tables.) How do you find $v$, and how do you test adjacency of $u$ and $w$?
Let the number of edges from $A$ to $B$ be $x$, the number from $B$ to $C$ be $y$, and the number of edges from $A$ to $C$ be $z$, with $x < y < z$. The bound $d=O(\sqrt{m})$ on the degeneracy of arbitrary graphs would translate in this case to $d=O(\sqrt z)$. Either prove a tighter bound on the degeneracy of a graph with this structure, or prove that (for all $x$, $y$, and $z$) there exist tripartite graphs for which the degeneracy is $\Theta(\sqrt{z})$.
In terms of $x$, $y$, and $z$, what is the best bound you can prove on the total time used by this triangle-finding algorithm?