Paley graph

Definition

Suppose $q$ is a prime power such that $q\equiv 1(\mathrm{mod}4)$. The Paley graph on $q$ vertices is defined as follows:

1. The vertex set is identified with the elements of the field ${\mathbb{F}}_q$ of $q$ elements. This field is unique up to field isomorphism.
2. Given any two distinct vertices $a,b\in {\mathbb{F}}_q$, $a$ and $b$ are defined to be adjacent if and only if $a-b$ is a square in ${\mathbb{F}}_q^{*}$.

The significance of $q\equiv 1(\mathrm{mod}4)$ is that this forces -1 to be a square, hence $a-b$ is a square if and only if $b-a$ is a square. This is necessary because we want the definition of adjacency to be symmetric in the two vertices.

For a prime power $q\equiv 3(\mathrm{mod}4)$, we can consider instead the Paley digraph.