ein regulärer GraphG mit den folgenden Eigenschaften, der weder der vollständige noch der leere Graph ist.

Es existieren zwei ganze Zahlen s, t ≥ 0 so, daß für je zwei beliebige Ecken u und v aus G die Anzahl derjenigen Ecken, die zu u und v gleichzeitig adjazent sind, stets s beträgt, falls u und v adjazent sind, und stets t ist, falls u und v nicht adjazent sind. Ist G zusätzlich vom Regularitätsgrad r und der Ordnung n, so nennt man die Zahlen n, r, s und t die Parameter des stark regulären Graphen G.

Einfache Beispiele von stark regulären Graphen sind die vollständigen bipartiten GraphenK_{n, n}(n ≥ 2) mit den Parametern 2n, n, 0 und n, und der berühmte Petersen-Graph mit den Parametern 10, 3, 0 und 1. Ist G ein stark regulärer Graph, so erkennt man ohne Mühe, daß auch sein Komplementärgraph \(\bar{G}\) stark regulär ist. Liegt ein stark regulärer Graph vom Regularitätsgrad r vor, so läßt sich auch folgende Aussage recht leicht bestätigen: Für den Parameter t gilt genau dann t = 0, wenn G aus der disjunkten Vereinigung von vollständigen Graphen der Ordnung r + 1 besteht. Schwerer nachzuweisen ist der folgende Satz von S.S. Shrikhande und Bhagawandas aus dem Jahre 1965.

Ein regulärer und zusammenhängender Graph G ist genau dann stark regulär, wenn er genau drei verschiedene Eigenwerteν₁, ν₂undν₃besitzt.

Gilt für diese drei Eigenwerte ν₁ >ν₂ >ν₃, so besteht folgender Zusammenhang mit den Parametern von G: Es gilt r = ν₁, s = r + ν₂ + ν₃ + ν₂ν₃, und t = r + ν₂ν₃. A.E. Brouwer und D.M. Messner zeigten 1985, daß stark reguläre Graphen vom Regularitätsgrad r die Zusammenhangszahl r besitzen. Die Klasse der stark regulären Graphen, die 1963 von R.C. Bose und unabhängig 1964 von D.G. Higman eingeführt worden ist, weist interessante Zusammenhänge mit der endlichen Geometrie auf.