Maximum density of a double-node-colored graph Let $G$ be a graph with the following properties.  $C$ is a set of colors.  The nodes of $G$ are $C \choose 2$.  For any node $v$, the neighborhood of $v$ is rainbow -- that is, for any two nodes $x, y$ adjacent to $v$, the two colors of $x$ are different from the two colors of $y$.
What is the maximum number of edges $G$ might have (up to constant factors -- big O is fine)?  Have these graphs been studied before?
 A: [Self-Answer]
The answer is $\Theta(c^3)$.  The upper bound is trivial.  To construct a graph with $\Omega(c^3)$ edges, randomly add $c/100$ edges incident to each node, and say that an edge $(u, v)$ is "bad" if $v$ shares a color with another of $u$'s neighbors (or vice versa), and "good" otherwise.  A simple probability calculation shows that any given edge is bad with only constant probability, so (in expectation) at most a constant fraction of the edges are bad.  We can then delete all bad edges, and we obtain a graph satisfying the constraints with (in expectation) $\Omega(c^3)$ edges.
A: Here is an almost optimal explicit example.
It is well known that the edges of $K_c$ can be colored properly in $c-1$ colors if $c$ is even, and in $c$ colors if $c$ is odd. Now, each edge of $K_c$ is a vertex of $G$; connect it by an edge in $G$ with all edges of $K_c$ of the same color. Then the degree of each vertex is just 1 less than the potentially maximal one.
Just in case: how to color the edges. If $c$ is odd, regard the vertices as the vertices of a regular $c$-gon; the sides and diagonals parallel to each other form a color. If $c$ is even, regard the vertices as the vertices of a regular $(c-1)$-gon and its center; each color consists of one `radius' from the center, together with all sides and diagonals perpendicular to this radius.
