Schläfli graph
title: "Schläfli graph" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["individual-graphs", "regular-graphs", "strongly-regular-graphs"] topic_path: "general/individual-graphs" source: "https://en.wikipedia.org/wiki/Schläfli_graph" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0
::data[format=table title="infobox graph"]
| Field | Value |
|---|---|
| name | Schläfli graph |
| image | [[File:Schläfli graph.svg |
| vertices | 27 |
| edges | 216 |
| diameter | 2 |
| radius | 2 |
| girth | 3 |
| automorphisms | 51840 |
| chromatic_number | 9 |
| properties | Strongly regular |
| Claw-free | |
| Hamiltonian | |
| Polytopal | |
| :: |
| name = Schläfli graph | image = [[File:Schläfli graph.svg|200px]] | vertices = 27 | edges = 216 | diameter = 2 | radius = 2 | girth = 3 | automorphisms = 51840 | chromatic_number = 9 | properties = Strongly regular Claw-free Hamiltonian Polytopal
In the mathematical field of graph theory, the Schläfli graph, named after Ludwig Schläfli, is a 16-regular undirected graph with 27 vertices and 216 edges. It is a strongly regular graph with parameters srg(27, 16, 10, 8).
Construction
::figure[src="https://upload.wikimedia.org/wikipedia/commons/8/8e/Up_2_21_t0_E6.svg" caption="221 polytope]]. This symmetric projection contains 2 rings of 12 vertices, and 3 vertices coinciding at the center."] ::
The intersection graph of the 27 lines on a cubic surface is a locally linear graph that is the complement of the Schläfli graph. That is, two vertices are adjacent in the Schläfli graph if and only if the corresponding pair of lines are skew.
The Schläfli graph may also be constructed from the system of eight-dimensional vectors :(1, 0, 0, 0, 0, 0, 1, 0), :(1, 0, 0, 0, 0, 0, 0, 1), and :(−1/2, −1/2, 1/2, 1/2, 1/2, 1/2, 1/2, 1/2), and the 24 other vectors obtained by permuting the first six coordinates of these three vectors. These 27 vectors correspond to the vertices of the Schläfli graph; two vertices are adjacent if and only if the corresponding two vectors have 1 as their inner product.
Alternately, this graph can be seen as the complement of the collinearity graph of the generalized quadrangle GQ(2, 4).
Subgraphs and neighborhoods
The neighborhood of any vertex in the Schläfli graph forms a 16-vertex subgraph in which each vertex has 10 neighbors (the numbers 16 and 10 coming from the parameters of the Schläfli graph as a strongly regular graph). These subgraphs are all isomorphic to the complement graph of the Clebsch graph. Since the Clebsch graph is triangle-free, the Schläfli graph is claw-free. It plays an important role in the structure theory for claw-free graphs by .
Any two skew lines of these 27 belong to a unique Schläfli double six configuration, a set of 12 lines whose intersection graph is a crown graph in which the two lines have disjoint neighborhoods. Correspondingly, in the Schläfli graph, each edge uv belongs uniquely to a subgraph in the form of a Cartesian product of complete graphs K6 \square K2 in such a way that u and v belong to different K6 subgraphs of the product. The Schläfli graph has a total of 36 subgraphs of this form, one of which consists of the zero-one vectors in the eight-dimensional representation described above.
Ultrahomogeneity
A graph is defined to be k-ultrahomogeneous if every isomorphism between two of its induced subgraphs of at most k vertices can be extended to an automorphism of the whole graph. If a graph is 5-ultrahomogeneous, it is ultrahomogeneous for every k; the only finite connected graphs of this type are complete graphs, Turán graphs, 3 × 3 rook's graphs, and the 5-cycle. The infinite Rado graph is countably ultrahomogeneous. There are only two connected graphs that are 4-ultrahomogeneous but not 5-ultrahomogeneous: the Schläfli graph and its complement. The proof relies on the classification of finite simple groups.
Notes
References
- {{citation | last = Buczak | first = J. M. J. | publisher = University of Oxford | series = D.Phil. thesis | title = Finite Group Theory | year = 1980}}. As cited by .
- {{citation | last1 = Bussemaker | first1 = F. C. | last2 = Neumaier | first2 = A. | doi = 10.1090/S0025-5718-1992-1134718-6 | issue = 200 | journal = Mathematics of Computation | pages = 583–608 | title = Exceptional graphs with smallest eigenvalue-2 and related problems | volume = 59 | year = 1992| bibcode = 1992MaCom..59..583B | doi-access = free
- {{citation | last = Cameron | first = Peter Jephson | journal = Journal of Combinatorial Theory, Series B | pages = 168–179 | title = 6-transitive graphs | volume = 28 | issue = 2 | year = 1980 | doi=10.1016/0095-8956(80)90063-5| doi-access = free
- {{citation | last1 = Cameron | first1 = Peter Jephson | last2 = van Lint | first2 = Jacobus Hendricus | isbn = 978-0-521-41325-1 | page = 35 | publisher = Cambridge University Press | series = London Mathematical Society student texts | title = Designs, graphs, codes and their links | volume = 22 | year = 1991}}.
- {{citation | last1 = Chudnovsky | first1 = Maria | author1-link = Maria Chudnovsky | last2 = Seymour | first2 = Paul | author2-link = Paul Seymour (mathematician) | contribution = The structure of claw-free graphs | mr = 2187738 | location = Cambridge | pages = 153–171 | publisher = Cambridge Univ. Press | series = London Math. Soc. Lecture Note Ser. | title = Surveys in combinatorics 2005 | url = http://publications.ias.edu/files/2005/02/u:4_p:180____claws_survey.pdf | volume = 327 | year = 2005 | access-date = 2010-07-30 | archive-date = 2010-06-09 | archive-url = https://web.archive.org/web/20100609234905/http://publications.ias.edu/files/2005/02/u:4_p:180____claws_survey.pdf | url-status = dead
- {{citation | last = Devillers | first = Alice | publisher = Université Libre de Bruxelles | series = Ph.D. thesis | title = Classification of some homogeneous and ultrahomogeneous structures | year = 2002}}.
- {{citation | last1 = Holton | first1 = D. A. | last2 = Sheehan | first2 = J. | pages = 270–271 | publisher = Cambridge University Press | title = The Petersen Graph | title-link = The Petersen Graph | year = 1993}}.
References
- {{harvtxt. Holton. Sheehan. 1993.
- {{harvtxt. Bussemaker. Neumaier. 1992.
- {{harvtxt. Cameron. van Lint. 1991. Note that Cameron and van Lint use an alternative definition of these graphs in which both the Schläfli graph and the Clebsch graph are [[complement (graph theory). complemented]] from their definitions here.
- {{harvtxt. Buczak. 1980; {{harvtxt. Cameron. 1980; {{harvtxt. Devillers. 2002.
::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::