I'm working out of Godsil and Royle's Algebraic Graph Theory text, and I'm trying to understand Paley graphs. My book gives as a definition the following:
Let $q$ be a prime power such that $q\equiv 1\pmod{4}$. The Paley graph $P(q)$ has as vertex set the elements of the finite field $GF(q)$, with two vertices adjacent if and only if their difference is a nonzero square in $GF(q)$.
In case it isn't clear, $GF(q)=\mathbb{F}_q$. My text also includes the following sentence:
The congruence condition on $q$ implies that $-1$ is a square in $GF(q)$, and hence the graph is undirected.
My book doesn't provide any illustrations of Paley graphs so I tried to contruct a couple. First, I made $P(5)\cong C_5$. This is very straightforward and didn't present any problems. Next, I tried to construct $P(9)$ and here I just don't understand what to do.
First, I computed the nonzero squares mod $9$. There are only three: $1,4,7$. Specifically $ (\pm 1)^2\equiv1 \qquad 2^2\equiv 4\equiv 7^2 \qquad 4^2\equiv7\equiv5^2 \pmod{4} $ First, notice that by the extra note, $8$ should be a square mod $9$, but that isn't the case. I have determined that, by Fermat's Little Theorem, if $q$ is a prime number rather than a prime power, this would be true. Is my text just incorrect or am I misunderstanding something?
Second, I tried to construct the actual graph. I started by labeling $9$ vertices $0,1,\dotsc,8$ in a circle. Then because $1$ is a square, I added edges around the entire thing, making a $9$-cycle. Because a Paley graph is supposed to be strongly regular, by examining the edges of a single vertex, I gain information about every other vertex. So consider the vertex labeled $0$. From the above, there are edges $01$ and $80$. Because $4$ is a square, there should be edges $04$ and $05$. Because $7$ is a square, there should be edges $02$ and $07$. Similarly, there should be $4$ edges for each vertex in addition to the $2$ that come from $1$ being a square, each corresponding to adding or subtracting $4$ or $7$.
However, the actual Paley graph on $9$ vertices is highly asymmetric. There's an image here (I'm not sure how to add an image to a post). http://mathworld.wolfram.com/PaleyGraph.html Labeling the northernmost vertex $0$ and labeling each consecutive vertex counterclockwise shows that there are edges $01, 08, 02$, and $04$ all incident with vertex $0$. But notice that there is not an edge $24$. However, $2-4\equiv 7\pmod{9}$ which is a square mod $9$. There are numerous additional edges that are not present, but should be according to the definition. Furthermore, $8$ is not a square mod $9$. so how can this graph be undirected? I've been playing with this for a long time and I just don't understand how the image on the link given corresponds to the $P(9)$ given by the definition. Can anyone offer any help?