Is there a citable proof of the following result (or perhaps a generalization of it)?
Lemma 1. Let $G=(V, E)$ be a proper interval graph. Let $G^k=(V, E^k)$ be the $k$th power of $G$. Then $|E^k| = O(k|E|)$.
(An interval graph is a graph whose vertices correspond to real intervals, with edges between pairs of intervals that intersect. An interval graph is proper if none of its intervals is a subset of another. The $k$th power of $G$ has an edge $(i, j)$ for each pair of distinct vertices that are at distance at most $k$ from each other.)
The closest reference I've found is a paper that presents a linear-time algorithm for computing an interval representation of $G^2$ given $G$, but as far as I can tell it it says nothing about the size of $E^2$.
For the interested, here's a sketch of a proof of the lemma.
Proof sketch. Let $V=\{v_1, v_2, \ldots, v_n\}$ be the vertices (intervals) of $V$ in increasing order. (So the left endpoints are strictly increasing, as are the right endpoints.) Consider the vertices to be ordered from "left" to "right" and the edges to be directed from left to right. For each integer $d\ge 0$ let $L_d$ be the "layer" of vertices at distance $d$ from $v_1$. If $L_d$ is non-empty, let $r_d$ be the rightmost point in $L_d$, so layer $L_{d+1}$ is comprised of the neighbors of $r_d$ to the right of $r_d$.
For $d\ge 1$, if $L_d$ is non-empty, each interval in $L_d$ contains the right endpoint of interval $r_{d-1}$. And $L_0=\{v_1\}$. So each $L_d$ forms a clique in $G$, implying $$|E| \ge \sum_{d\ge 0} {|L_d| \choose 2}.~~~~~~~(1)$$
Now consider $E^k$. Each edge in $E$ advances at most one layer, so each edge in $E^k$ advances at most $k$ layers. That is, if an edge $(v_a, v_b)$ with $a<b$ in $E^k$ has endpoint $v_a$ in layer $L_{d}$, then its other endpoint $v_b$ is in $L_{d+i}$ where $0\le i\le k$. So the number of edges in $E^k$ is at most $$\sum_{d \ge 0} \sum_{i=0}^k |L_d|\times |L_{d+i}| \le \sum_{d\ge 0} \sum_{i=0}^k|L_d|^2 + |L_{d+i}|^2 \le (2k+2) \sum_{d\ge 0} |L_d|^2 = O(k|E|).$$ The last step uses the lower bound (1) above.$~~~~\Box$.
Note that the lemma is tight in the sense that for the interval graph formed by a single path $v_1\to v_2\to\cdots \to v_n$, for $k\le n$ we have $|E^k| = \Theta(k|E|)$.
