Edges in a line graph Suppose I have a graph $G$, with $E$ edges and $V$ vertices. I now construct its line graph, $L(G)$.
The number of vertices in $L(G)$ has to be $E$ by the definition of a line graph. But what's the maximum number of edges in $L(G)$? I'm interested in the asymptotic worst case, that is, the big-O of the edge count in terms of $E$ and $V$.
My current guess is $O(E^2)$, which is the worst case if every edge is adjacent. But if $G$ is anything bigger than $K_3$ then I know this won't be the case. So it seems like it should be possible to reduce this further.
 A: In a star, all the edges are adjacent.
A: The best asymptotic bound we can put on the number of edges in the line graph is $O(EV)$ (actually, the product $EV$ by itself is an upper bound).
To get this bound, note that each of the $E$ edges of $L(G)$ has degree less than $2V$, since it shares each of its endpoints with fewer than $V$ edges. So the sum of degrees in $L(G)$ is at most $2EV$, and this is twice the number of edges.
We can achieve $\frac12 E(V-2) = \Omega(EV)$ edges in the line graph for a range of values of $E$ relative to $V$, by taking a complete bipartite graph. The complete bipartite graph $K_{a,b}$ has $a+b$ vertices and $ab$ edges. In the line graph $L(K_{a,b})$, there are $ab$ vertices, and each has degree $a+b-2$ (each edge of $K_{a,b}$ is incident to $a-1$ other edges on the side of size $a$ and $b-1$ other edges on the side of size $b$), so the degree sum is $ab(a+b-2) = E(V-2)$. The number of edges in $L(K_{a,b})$ is half that.
(In particular, the star, which is $K_{1,n-1}$, achieves this bound.)

As a consequence of the construction above, we can find a graph $L(G)$ with $V$ vertices and $E$ edges such that $L(G)$ has at least$\frac14E(V-2) = \Omega(VE)$ edges, for any choice of $E$ and $V$ with $V-1 \le E \le \binom{V}{2}$. Just consider the sequence of graphs
$$
   K_{1,V-1}, K_{2,V-2}, K_{3,V-3}, \dots, K_{\lfloor V/2 \rfloor, \lceil V/2 \rceil}.
$$
Each graph has at least half as many edges as the next, and the last graph has more than $\frac12\binom{V}{2}$ edges. So for any $E$, we can find a graph $G$ in this sequence with $V$ vertices and some number of edges between $\frac12E$ and $E$. That $G$'s line graph will have at least $\frac12 (\frac12E)(V-2)$ edges, and if we add edges arbitrarily to get a graph $G'$ with exactly $E$ edges, its line graph will still have at least $\frac14 E(V-2)$ edges.
In graphs where $E < V-1$, the $O(E^2)$ upper bound is better, and we can achieve it by a star on $E+1$ vertices together with $V-E-1$ isolated vertices.
