In mathematics, Paley graphs are undirected graphs constructed from the members of a suitable finite field by connecting pairs of elements that differ by a quadratic residue.

Sachs was interested in them for their self-complementarity properties,[2] while Erdős and Rényi studied their symmetries.

They were introduced by Graham & Spencer (1971) (independently of Sachs, Erdős, and Rényi) as a way of constructing tournaments with a property previously known to be held only by random tournaments: in a Paley digraph, every small subset of vertices is dominated by some other vertex.

This choice of q implies that in the unique finite field Fq of order q, the element  −1 has a square root.

These are matrices whose coefficients are ±1, with zero on the diagaonal, that give a scalar multiple of the identity matrix when multiplied by their transpose.

They can be calculated using the quadratic Gauss sum or by using the theory of strongly regular graphs.

The Paley digraph is the directed graph with vertex set V = Fq and arc set The Paley digraph is a tournament because each pair of distinct vertices is linked by an arc in one and only one direction.

The Paley digraph leads to the construction of some antisymmetric conference matrices and biplane geometries.

More generally, if any Paley graph of order q could be embedded so that all its faces are triangles, we could calculate the genus of the resulting surface via the Euler characteristic as

Specifically, Mohar conjectures that the Paley graphs of square order can be embedded into surfaces with genus where the o(1) term can be any function of q that goes to zero in the limit as q goes to infinity.

[12] White (2001) finds embeddings of the Paley graphs of order q ≡ 1 (mod 8) that are highly symmetric and self-dual, generalizing a natural embedding of the Paley graph of order 9 as a 3×3 square grid on a torus.

However the genus of White's embeddings is higher by approximately a factor of three than Mohar's conjectured bound.