In der Graphentheorie ist der Clebsch-Graph ein ungerichteter Graph mit 16 Knoten und 40 Kanten. Er ist benannt nach Alfred Clebsch, der ihn 1868 betrachtete. Die Bezeichnung Greenwood–Gleason-Graph wird dazu synonym verwendet.^[1][2]

Der Graph kann wie folgt konstruiert werden: Die Knoten ${\displaystyle v_{i}\in V}$ des fünfdimensionalen Würfels seien Binärdarstellungen der festen Länge ${\displaystyle 5}$ der ganzen Zahlen von ${\displaystyle 0}$ bis ${\displaystyle 2^{5}-1=31}$, also die Zeichenfolgen:

${\displaystyle v_{0}=}$ "00000" → 0
${\displaystyle v_{1}=}$ "00001" → 1
${\displaystyle v_{2}=}$ "00010" → 2
…
${\displaystyle v_{31}=}$ "11111" → 31

Die Kantenmenge des Würfels ist dann die Relation ${\displaystyle A\subset V\times V}$ mit ${\displaystyle (x,y)\in A\Leftrightarrow x}$ und ${\displaystyle y}$ unterscheiden sich in genau einer Stelle ihrer Darstellungen. Daraus erhält man den Clebsch-Graphen durch Identifikation antipodaler Eckpunkte, also Punkten, die sich in allen fünf Stellen unterscheiden.

Graphentheoretische Eigenschaften

Der Graph ist stark regulär. Der Minimalgrad und der Maximalgrad sind gleich und haben den Wert ${\displaystyle 5}$, also ist der Graph nicht eulersch. Der Graph ist hamiltonsch und nicht planar. Der Komplementgraph ist ebenfalls stark regulär.

Algebraische Eigenschaften

Der Graph ist ein Cayleygraph. Seine Automorphismengruppe hat die Ordnung ${\displaystyle 1920}$ und ist isomorph zur Coxeter-Gruppe ${\displaystyle D_{5}}$. Der Graph ist knoten-, kanten- und distanztransitiv.

• 
  Der Clebsch-Graph ist hamiltonsch.
• 
  Die achromatische Zahl des Clebsch-Graphen ist ${\displaystyle 8}$.
• 
  Die chromatische Zahl des Clebsch-Graphen ist ${\displaystyle 4}$.
• 
  Der chromatische Index des Clebsch-Graphen ist ${\displaystyle 5}$.

1. ↑ Alfred Clebsch: Ueber die Flächen vierter Ordnung, welche eine Doppelcurve zweiten Grades besitzen. In: Journal für Mathematik. Band 69, 1868, S. 142–184. 
2. ↑ The Clebsch Graph. In: MathWorld. Abgerufen am 22. Oktober 2023 (englisch).