Paley graph

Definition

Suppose $q$ is a prime power such that $q\equiv 1{\pmod {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{\pmod {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{\pmod {4}}$, we can consider instead the Paley digraph.