Editing Ramanujan graph (section)

=== Explicit examples ===

* The [[complete graph]] <math>K_{d+1}</math> has spectrum <math>d, -1, -1, \dots, -1</math>, and thus <math>\lambda(K_{d+1}) = 1</math> and the graph is a Ramanujan graph for every <math>d > 1</math>. The [[complete bipartite graph]] <math>K_{d,d}</math> has spectrum <math>d, 0, 0, \dots, 0, -d</math> and hence is a bipartite Ramanujan graph for every <math>d</math>.
* The [[Petersen graph]] has spectrum <math>3, 1, 1, 1, 1, 1, -2, -2, -2, -2</math>, so it is a 3-regular Ramanujan graph. The [[Regular icosahedron|icosahedral graph]] is a 5-regular Ramanujan graph.<ref>{{Cite web|last=Weisstein|first=Eric W.|title=Icosahedral Graph|url=http://mathworld.wolfram.com/IcosahedralGraph.html|access-date=2019-11-29|website=mathworld.wolfram.com|language=en}}</ref>
* A [[Paley graph]] of order <math>q</math> is <math>\frac{q-1}{2}</math>-regular with all other eigenvalues being <math>\frac{-1\pm\sqrt{q}}{2}</math>, making Paley graphs an infinite family of Ramanujan graphs.
* More generally, let <math>f(x)</math> be a degree 2 or 3 polynomial over <math>\mathbb{F}_q</math>. Let <math>S = \{f(x)\, :\, x \in \mathbb{F}_q\}</math> be the image of <math>f(x)</math> as a multiset, and suppose <math>S = -S</math>. Then the [[Cayley graph]] for <math>\mathbb{F}_q</math> with generators from <math>S</math> is a Ramanujan graph.

Mathematicians are often interested in constructing infinite families of <math>d</math>-regular Ramanujan graphs for every fixed <math>d</math>. Such families are useful in applications.