The graphs that bear his name are constructed as follows:
Given a finite field *F* with *q* elements,
make a graph with vertex set *F* where two vertices
are joined when their difference is a square in the field.
This is an undirected graph when *q* is congruent 1 (mod 4).

For *q* = 4*t* + 1, the parameters are
*v* = 4*t* + 1,
*k* = 2*t*,
λ = *t* − 1,
μ = *t*.

Examples (*q* = 5 and *q* = 9):

For *q* = 13 the Paley graph is locally a hexagon, so that
the graph is a quotient of the hexagonal grid:

(More generally, the graph on the elements of GF(q), where q=6t+1,
where x and y are adjacent when (y−x)^{6} = 1,
is locally a hexagon, unless q is a power of 7.)

Paley graphs are isomorphic to their complements: if *a* is
a nonsquare, then the map that sends *x* to *ax* is
an isomorphism from the graph to its complement.

The subgraph induced on the neighbors of 0 (that is, on the set of squares)
has full group generated by the maps *x* ↦ *ax* where *a*
is a nonzero square, the field automorphisms,
and the map *x* ↦ *x*^{−1}
(Muzychuk & Kovácz, 2005). If *q* > 9 it has order *e*(*q*−1).

A small table with independence numbers and chromatic numbers:

q | 5 | 9 | 13 | 17 | 25 | 29 | 37 | 41 | 49 | 53 | 61 | 73 | 81 | 89 | 97 | 101 | 109 | 113 | 121 | 125 | 137 | 149 | 157 | 169 | 173 | 181 | 193 | 197 | |

α | 2 | 3 | 3 | 3 | 5 | 4 | 4 | 5 | 7 | 5 | 5 | 5 | 9 | 5 | 6 | 5 | 6 | 7 | 11 | 7 | 7 | 7 | 7 | 13 | 8 | 7 | 7 | 8 | |

χ | 3 | 3 | 5 | 6 | 5 | 8 | 10 | 9 | 7 | 11 | 13 | 15 | 9 | 18 | 17 | 21 | 19 | 17 | 11 | 18 | 20 | 22 | 23 | 13 | 22 | 26 | 28 | 25 |

The chromatic numbers for q=125,173,197 are due to Geoffrey Exoo (pers. comm.).

Since the Paley graphs are self-complementary, their clique numbers
equal their independence numbers.
By the Hoffman bound, the independence number is at most sqrt(*q*).
For prime *q*, Hanson and Petridis improved this upper bound
to roughly sqrt(*q/2*), more precisely
(1+sqrt(2*q*−1))/2. Equality holds for *q*=5, 13, 41.

A much stronger result is found in
A. Blokhuis,
*On subsets of GF(q ^{2}) with square differences*,
Indag. Math.

For *q* = *r*^{2} with *r* = 4*t*±1,
smaller maximal cliques (of size 2*t*+1) are constructed in
R. D. Baker, G. L. Ebert, J. Hemmeter, A. J. Woldar,
*Maximal cliques in the Paley graph of square order*,
J. Statist. Plann. Inference **56** (1996) 33-38.
They conjecture that no maximal clique in the Paley graph of order
*r*^{2} has size strictly between 2*t*+1 and *r*.

See also M. Kiermaier & S. Kurz,Maximal integral point sets in affine planes over finite fields, Discr. Math.309(2009) 4564-4575, and S. Goryainov, V. V. Kabanov, L. Shalaginov & A. Valyuzhenich,On eigenfunctions and maximal cliques of Paley graphs of square order, Finite Fields Appl.52(2018) 361–369, and S. Goryainov, A. Masley & L. Shalaginov,On a correspondence between maximal cliques in Paley graphs of square order, Discr. Math.345(2022) 112853.

size | q |
---|---|

2 | 5 |

3 | 9-25 |

4 | 29-81 |

5 | 89-373, 401-409, 433, 457, 569, 953 |

6 | 389-397, 421, 449, 461-557, 577-941, 961-1213, 1229, 1249-1289, 1321, 1369, 1409, 1553, 1669 |

7 | 1217, 1237, 1297-1301, 1361, 1373-1381, 1429-1549, 1597-1657, 1681-2029 |

Similarly, for Paley tournaments P(*q*) one has:

size | q |
---|---|

2 | 3 |

3 | 7-11 |

4 | 19-59, 103 |

5 | 67-83, 107-311, 343, 379 |

6 | 331, 347-367, 383-1151, 1171, 1223, 1331, 1723 |

7 | 1163, 1187, 1231-1327, 1367-1699, 1747-2039 |

See
Changwoo Lee, *The domination number of a tournament*,
Kangweon-Kyungki Math. J. **9** (2001) 21-28.