Paley graph

Definition

Suppose $q$ is a prime power such that $q\equiv 1{\pmod {4}}$. The Paley graph on $q$ vertices, denoted $P_{q}$ or $QR(q)$, 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.

Arithmetic functions

Size measures

Function	Value	Explanation
size of vertex set	$q$	By definition, the vertex set is the underlying set of a field of size $q$
size of edge set	$q(q-1)/4$	The number of quadratic residues is $(q-1)/2$, hence this is the degree of each vertex. We now use the handshaking lemma.

Numerical invariants associated with vertices

Since the graph is a vertex-transitive graph, any numerical invariant associated to a vertex must be equal on all vertices of the graph. Below are listed some of these invariants:

Function	Value	Explanation
degree of a vertex	$(q-1)/2$	This equals the number of quadratic residues in $\mathbb {F} _{q}^{\ast }$, which is the size of the image of the square map $x\mapsto x^{2}$, whose domain has size $q-1$ and kernel has size 2. The image thus has size $(q-1)/2$. Note that we are using that $q$ is odd.
eccentricity of a vertex	2	Follows from every element of a finite field is expressible as a sum of two squares

Other numerical invariants

Function	Value	Explanation
clique number	no easy formula, but generally grows with $q$	Note that $q=5$ is the only case where the clique number is 2; for $q\geq 9$, the clique number is at least 3 because of the presence of adjacent quadratic residues -- the number of adjacent quadratic residues is $(q-5)/4$. $q=17$ is the largest value for which the clique number is 3. By Ramsey theory, we know that if $q\geq R(m,m)$, then the clique number is at least $m$.
independence number	same as clique number	The two numbers are equal because the Paley graph is a self-complementary graph and independence number equals clique number of complement
chromatic number	Fill this in later	Precise formula unclear, but the fact that self-complementary graph implies chromatic number is at least equal to square root of size of vertex set puts a lower bound, namely the smallest integer greater than or equal to ${\sqrt {q}}$.
radius of a graph	2	Due to vertex-transitivity, the radius equals the eccentricity of any vertex, which has been computed above.
diameter of a graph	2	Due to vertex-transitivity, the diameter equals the eccentricity of any vertex, which has been computed above.
girth of a graph	3 (except the case of $P_{5}$)	The girth of $P_{5}$ is 5. Note that for all higher $q$, the girth of the graph is 3, due to the fact that there are $(q-5)/4$ pairs of nonzero quadratic residues that differ by 1, and this number is positive whenever $q>5$.
circuit rank	$q(q-5)/4+1$ $=(q-1)(q-4)/4$	The circuit rank is number of edges - number of vertices + number of connected components. This becomes $q(q-1)/4-q+1$ which simplifies to $q(q-5)/4+1$.