Definition. (Paley graphs). Let $q = p^n$ be a prime power with $q \equiv 1 (\mod 4)$. We define the Paley graph $P_q$ to be the graph with set of vertices $V = \mathbb{F}_q$ and the edge relation defined by $xRy$ if and only if $x\neq y$ and $(x - y)$ is a square.
Question. How can we compute the number of edges of the paley graph $P_q$ where $q=p^n$ for some prime number $p$?
The multiplicative group of $\mathbb{F}_{q}$ is cyclic, so as long as $q$ is odd, half of the nonzero elements are squares. If you consider a fixed $x \in \mathbb{F}_{q}$, how many different elements do you obtain by considering the set $\{ x-y : y \in \mathbb{F}_{q}, y \neq x\}$? How many of them are squares? What does this tell you about the degree of $x$ in $P_{q}$? And about the total number of edges in $P_{q}$?