Clebsch graph

<h2 id="construction">Construction</h2>
The dimension-5 <a href="/facts/Folded_cube_graph/wpQyUsh8">folded cube graph</a> (the 5-regular Clebsch graph) may be constructed by adding edges between opposite pairs of vertices in a 4-dimensional hypercube graph. (In an n-dimensional hypercube, a pair of vertices are opposite if the shortest path between them has n edges.) Alternatively, it can be formed from a 5-dimensional hypercube graph by <a href="/facts/Vertex_identification/PRqKXEkj">identifying</a> together (or contracting) every opposite pair of vertices.
Another construction, leading to the same graph, is to create a vertex for each element of the <a href="/facts/Finite_field/UkMGJo3m">finite field</a> GF(16), and connect two vertices by an edge whenever the difference between the corresponding two field elements is a <a href="/facts/Cube_(algebra)/SqmlEEog">perfect cube</a>.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a>
The dimension-5 <a href="/facts/Halved_cube_graph/SpXsyEWq">halved cube graph</a> (the 10-regular Clebsch graph) is the <a href="/facts/Complement_(graph_theory)/IdHUPFr3">complement</a> of the 5-regular graph. It may also be constructed from the vertices of a 5-dimensional hypercube, by connecting pairs of vertices whose <a href="/facts/Hamming_distance/MgdtbYPo">Hamming distance</a> is exactly two. This construction is an instance of the construction of <a href="/facts/Frankl%25E2%2580%2593R%25C3%25B6dl_graph/WUs4uLQh">Frankl–Rödl graphs</a>. It produces two subsets of 16 vertices that are disconnected from each other; both of these <a href="/facts/Half-square/35w3eF8a">half-squares</a> of the hypercube are <a href="/facts/Graph_isomorphism/SBjVIhwW">isomorphic</a> to the 10-regular Clebsch graph. Two copies of the 5-regular Clebsch graph can be produced in the same way from a 5-dimensional hypercube, by connecting pairs of vertices whose Hamming distance is exactly four.

<h2 id="properties">Properties</h2>
The 5-regular Clebsch graph is a <a href="/facts/Strongly_regular_graph/0GbdLwSd">strongly regular graph</a> of degree 5 with parameters 
 
 
 
 (
 v
 ,
 k
 ,
 λ
 ,
 μ
 )
 =
 (
 16
 ,
 5
 ,
 0
 ,
 2
 )
 
 
 {\displaystyle (v,k,\lambda ,\mu )=(16,5,0,2)}
 
.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a><a class="footnote-ref" id="fnref:7" href="#fn:7">7</a>
Its complement, the 10-regular Clebsch graph, is therefore also a strongly regular graph,<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a><a class="footnote-ref" id="fnref:9" href="#fn:9">9</a> with parameters 
 
 
 
 (
 16
 ,
 10
 ,
 6
 ,
 6
 )
 
 
 {\displaystyle (16,10,6,6)}
 
.
The 5-regular Clebsch graph is <a href="/facts/Hamiltonian_graph/MHjY2xoY">Hamiltonian</a>, <a href="/facts/Planar_graph/plREagr9">non planar</a> and <a href="/facts/Eulerian_graph/4l2G67c7">non Eulerian</a>. It is also both 5-<a href="/facts/K-vertex-connected_graph/EST9uf8W">vertex-connected</a> and 5-<a href="/facts/K-edge-connected_graph/vJN0po8s">edge-connected</a>. The <a href="/facts/Induced_subgraph/G3EUC0MQ">subgraph that is induced</a> by the ten non-neighbors of any vertex in this graph forms an <a href="/facts/Graph_isomorphism/SBjVIhwW">isomorphic</a> copy of the <a href="/facts/Petersen_graph/lLRxXpQs">Petersen graph</a>. 
It has <a href="/facts/Book_thickness/2hz3yIP7">book thickness</a> 4 and <a href="/facts/Queue_number/d2ENH4YC">queue number</a> 3.<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a>

The edges of the <a href="/facts/Complete_graph/AYD6hUqI">complete graph</a> K16 may be partitioned into three disjoint copies of the 5-regular Clebsch graph. Because the Clebsch graph is a <a href="/facts/Triangle-free_graph/8D3LJ44h">triangle-free graph</a>, this shows that there is a triangle-free three-coloring of the edges of K16; that is, that the <a href="/facts/Ramsey_number/VS6K8jGk">Ramsey number</a> R(3,3,3) describing the minimum number of vertices in a complete graph without a triangle-free three-coloring is at least 17. Greenwood & Gleason (1955) used this construction as part of their proof that R(3,3,3) = 17.<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a><a class="footnote-ref" id="fnref:12" href="#fn:12">12</a>
The 5-regular Clebsch graph may be <a href="/facts/Graph_coloring/J6HoBfP0">colored</a> with four colors, but not three: its largest <a href="/facts/Independent_set_(graph_theory)/ksu46kdz">independent set</a> has five vertices, not enough to partition the graph into three independent color classes. It contains as an <a href="/facts/Induced_subgraph/G3EUC0MQ">induced subgraph</a> the <a href="/facts/Gr%25C3%25B6tzsch_graph/Kb1vAwMq">Grötzsch graph</a>, the smallest <a href="/facts/Triangle-free_graph/8D3LJ44h">triangle-free</a> four-chromatic graph, and every four-chromatic induced subgraph of the Clebsch graph is a supergraph of the Grötzsch graph. More strongly, every triangle-free four-chromatic graph with no <a href="/facts/Induced_path/zfcIx9Sw">induced path</a> of length six or more is an induced subgraph of the Clebsch graph and an induced supergraph of the Grötzsch graph.<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a>
The 5-regular Clebsch graph is the <a href="/facts/Keller%2527s_conjecture/KXDD5E5w">Keller graph</a> of dimension two, part of a family of graphs used to find tilings of high-dimensional <a href="/facts/Euclidean_space/R2UbzmzM">Euclidean spaces</a> by <a href="/facts/Hypercube/q2mRPbIz">hypercubes</a> no two of which meet face-to-face.
The 5-regular Clebsch graph can be embedded as a <a href="/facts/Regular_map_(graph_theory)/4ahwy17x">regular map</a> in the orientable manifold of genus 5, forming pentagonal faces; and in the non-orientable surface of genus 6, forming tetragonal faces.

<h3>Algebraic properties</h3>
The <a href="/facts/Characteristic_polynomial/7m8roDqo">characteristic polynomial</a> of the 5-regular Clebsch graph is 
 
 
 
 (
 x
 +
 3
 
 )
 
 5
 
 
 (
 x
 −
 1
 
 )
 
 10
 
 
 (
 x
 −
 5
 )
 
 
 {\displaystyle (x+3)^{5}(x-1)^{10}(x-5)}
 
. Because this polynomial can be completely factored into linear terms with integer coefficients, the Clebsch graph is an <a href="/facts/Integral_graph/9rKeKBNb">integral graph</a>: its <a href="/facts/Spectral_graph_theory/tBttgGTh">spectrum</a> consists entirely of integers.<a class="footnote-ref" id="fnref:14" href="#fn:14">14</a> The Clebsch graph is the only graph with this characteristic polynomial, making it a graph determined by its spectrum.
The 5-regular Clebsch graph is a <a href="/facts/Cayley_graph/QxoxNnys">Cayley graph</a> with an automorphism group of order 1920, isomorphic to the <a href="/facts/Coxeter_group/bgzHFm1Q">Coxeter group</a> 
 
 
 
 
 D
 
 5
 
 
 
 
 {\displaystyle D_{5}}
 
. As a Cayley graph, its automorphism group acts transitively on its vertices, making it <a href="/facts/Vertex-transitive_graph/042b7rD7">vertex transitive</a>. In fact, it is <a href="/facts/Symmetric_graph/vPVWrnjb">arc transitive</a>, hence <a href="/facts/Edge-transitive_graph/fnK9oyEJ">edge transitive</a> and <a href="/facts/Distance-transitive_graph/HgH4heaB">distance transitive</a>. It is also <a href="/facts/Homogeneous_graph/BMXFLwj1">connected-homogeneous</a>, meaning that every isomorphism between two connected induced subgraphs can be extended to an automorphism of the whole graph.

<h2 id="gallery">Gallery</h2>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">J. J. Seidel, Strongly regular graphs with (−1,1,0) adjacency matrix having eigenvalue 3, Lin. Alg. Appl. 1 (1968) 281-298. <a href="/wiki/Adjacency_matrix" target="_blank">/wiki/Adjacency_matrix</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Clebsch, A. (1868), "Ueber die Flächen vierter Ordnung, welche eine Doppelcurve zweiten Grades besitzen", Journal für die reine und angewandte Mathematik, 69: 142–184. <a href="/wiki/Alfred_Clebsch" target="_blank">/wiki/Alfred_Clebsch</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">"The Clebsch Graph on Bill Cherowitzo's home page" (PDF). Archived from the original (PDF) on 2013-10-29. Retrieved 2011-05-21. <a href="https://web.archive.org/web/20131029202529/http://www-math.ucdenver.edu/~wcherowi/courses/m6023/shilpa.pdf" target="_blank">https://web.archive.org/web/20131029202529/http://www-math.ucdenver.edu/~wcherowi/courses/m6023/shilpa.pdf</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Greenwood, R. E.; Gleason, A. M. (1955), "Combinatorial relations and chromatic graphs", Canadian Journal of Mathematics, 7: 1–7, doi:10.4153/CJM-1955-001-4, MR 0067467. <a href="/wiki/Andrew_Gleason" target="_blank">/wiki/Andrew_Gleason</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">De Clerck, Frank (1997). "Constructions and Characterizations of (Semi)partial Geometries". Summer School on Finite Geometries. p. 6. <a href="http://cage.ugent.be/~fdc/potenza.ps" target="_blank">http://cage.ugent.be/~fdc/potenza.ps</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Godsil, C.D. (1995). "Problems in algebraic combinatorics" (PDF). Electronic Journal of Combinatorics. 2: 3. doi:10.37236/1224. Retrieved 2009-08-13. <a href="/wiki/Chris_Godsil" target="_blank">/wiki/Chris_Godsil</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Peter J. Cameron Strongly regular graphs on DesignTheory.org, 2001 <a href="http://designtheory.org/library/preprints/srg.pdf" target="_blank">http://designtheory.org/library/preprints/srg.pdf</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Weisstein, Eric W. "Clebsch Graph". From MathWorld—A Wolfram Web Resource. Retrieved 2009-08-13. <a href="http://mathworld.wolfram.com/ClebschGraph.html" target="_blank">http://mathworld.wolfram.com/ClebschGraph.html</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">"The Clebsch Graph on Bill Cherowitzo's home page" (PDF). Archived from the original (PDF) on 2013-10-29. Retrieved 2011-05-21. <a href="https://web.archive.org/web/20131029202529/http://www-math.ucdenver.edu/~wcherowi/courses/m6023/shilpa.pdf" target="_blank">https://web.archive.org/web/20131029202529/http://www-math.ucdenver.edu/~wcherowi/courses/m6023/shilpa.pdf</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Jessica Wolz, Engineering Linear Layouts with SAT. Master Thesis, University of Tübingen, 2018 <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Greenwood, R. E.; Gleason, A. M. (1955), "Combinatorial relations and chromatic graphs", Canadian Journal of Mathematics, 7: 1–7, doi:10.4153/CJM-1955-001-4, MR 0067467. <a href="/wiki/Andrew_Gleason" target="_blank">/wiki/Andrew_Gleason</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Sun, Hugo S.; Cohen, M. E. (1984), "An easy proof of the Greenwood–Gleason evaluation of the Ramsey number R(3,3,3)" (PDF), The Fibonacci Quarterly, 22 (3): 235–238, MR 0765316. <a href="http://www.fq.math.ca/Scanned/22-3/sun.pdf" target="_blank">http://www.fq.math.ca/Scanned/22-3/sun.pdf</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Randerath, Bert; Schiermeyer, Ingo; Tewes, Meike (2002), "Three-colourability and forbidden subgraphs. II. Polynomial algorithms", Discrete Mathematics, 251 (1–3): 137–153, doi:10.1016/S0012-365X(01)00335-1, MR 1904597. <a href="/wiki/Discrete_Mathematics_(journal)" target="_blank">/wiki/Discrete_Mathematics_(journal)</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">"The Clebsch Graph on Bill Cherowitzo's home page" (PDF). Archived from the original (PDF) on 2013-10-29. Retrieved 2011-05-21. <a href="https://web.archive.org/web/20131029202529/http://www-math.ucdenver.edu/~wcherowi/courses/m6023/shilpa.pdf" target="_blank">https://web.archive.org/web/20131029202529/http://www-math.ucdenver.edu/~wcherowi/courses/m6023/shilpa.pdf</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
</ol>

Clebsch graph open-in-new

Clebsch graph