Editing Desargues graph

{{Short description|Distance-transitive cubic graph with 20 nodes and 30 edges}}
{{Infobox graph
 | name = Desargues graph
 | image = [[Image:DesarguesGraph.svg|220px]]
 | namesake = [[Gérard Desargues]]
 | vertices = 20
 | edges = 30
 |automorphisms = 240 ({{math|S{{sub|5}} × S{{sub|2}}}})
 | chromatic_number = 2
 | chromatic_index = 3
 | girth = 6
 | radius = 5
 | diameter = 5
 | genus = 2
 | properties = [[Cubic graph|Cubic]]<br>[[Distance-regular graph|Distance-regular]]<br>[[hamiltonian graph|Hamiltonian]]<br>[[Bipartite graph|Bipartite]]<br>[[Symmetric graph|Symmetric]]
|book thickness=3
|queue number=2
}}

In the [[mathematics|mathematical]] field of [[graph theory]], the '''Desargues graph''' is a [[Distance-transitive graph|distance-transitive]], [[cubic graph]] with 20 [[Vertex (graph theory)|vertices]] and 30 edges.<ref>{{MathWorld|urlname=DesarguesGraph|title=Desargues Graph|mode=cs2}}</ref> It is named after [[Girard Desargues]], arises from several different combinatorial constructions, has a high level of symmetry, is the only known [[planar graph|non-planar]] cubic [[partial cube]], and has been applied in chemical databases.

The name "Desargues graph" has also been used to refer to a ten-vertex graph, the complement of the [[Petersen graph]], which can also be formed as the [[bipartite half]] of the 20-vertex Desargues graph.<ref>{{citation
  | last = Kagno | first = I. N.
  | title = Desargues' and Pappus' graphs and their groups
  | journal = American Journal of Mathematics
  | year = 1947
  | volume = 69
  | issue = 4
  | pages = 859–863
  | doi = 10.2307/2371806
  | jstor = 2371806
  | publisher = The Johns Hopkins University Press}}.</ref>

==Constructions==
There are several different ways of constructing the Desargues graph:
*It is the [[generalized Petersen graph]] {{math|''G''(10,3)}}. To form the Desargues graph in this way, connect ten of the vertices into a regular [[decagon]], and connect the other ten vertices into a ten-pointed star that connects pairs of vertices at distance three in a second decagon. The Desargues graph consists of the 20 edges of these two polygons together with an additional 10 edges connecting points of one decagon to the corresponding points of the other.
*It is the [[Levi graph]] of the [[Desargues configuration]]. This configuration consists of ten points and ten lines describing two [[Perspective (geometry)|perspective triangles]], their center of perspectivity, and their axis of perspectivity. The Desargues graph has one vertex for each point, one vertex for each line, and one edge for every incident point-line pair. [[Desargues' theorem]], named after 17th-century French mathematician [[Gérard Desargues]], describes a set of points and lines forming this configuration, and the configuration and the graph take their name from it.
*It is the [[bipartite double cover]] of the [[Petersen graph]], formed by replacing each Petersen graph vertex by a pair of vertices and each Petersen graph edge by a pair of crossed edges.
*It is the [[Kneser graph|bipartite Kneser graph]] {{math|''H''{{sub|5,2}}}}. Its vertices can be labeled by the ten two-element subsets and the ten three-element subsets of a five-element set, with an edge connecting two vertices when one of the corresponding sets is a subset of the other. Equivalently, the Desargues graph is the [[induced subgraph]] of the 5-dimensional hypercube determined by the vertices of weight 2 and weight 3. 
*The Desargues graph is [[Hamiltonian graph|Hamiltonian]] and can be constructed from the [[LCF notation]]: {{math|[5,−5,9,−9]{{sup|5}}}}.  As [[Paul Erdős|Erdős]] conjectured that for {{math|''k'' > 0}}, the subgraph of the {{math|(2''k'' + 1)}}-dimensional hypercube induced by the vertices of weight {{mvar|k}} and {{math|''k'' + 1}} is Hamiltonian, the Hamiltonicity of the Desargues graph is no surprise.  (It also follows from the stronger conjecture of Lovász that except for a few known counter-examples, all vertex-transitive graphs have Hamiltonian cycles.)

==Algebraic properties==
The Desargues graph is a [[symmetric graph]]: it has symmetries that take any vertex to any other vertex and any edge to any other edge. Its symmetry group has order 240, and is [[Graph isomorphism|isomorphic]] to the product of a [[symmetric group]] on 5 points with a group of order 2.

One can interpret this product representation of the symmetry group in terms of the constructions of the Desargues graph: the symmetric group on five points is the symmetry group of the Desargues configuration, and the order-2 subgroup swaps the roles of the vertices that represent points of the Desargues configuration and the vertices that represent lines. Alternatively, in terms of the [[bipartite Kneser graph]], the symmetric group on five points acts separately on the two-element and three-element subsets of the five points, and complementation of subsets forms a group of order two that transforms one type of subset into the other. The symmetric group on five points is also the symmetry group of the [[Petersen graph]], and the order-2 subgroup swaps the vertices within each pair of vertices formed in the double cover construction.

The generalized Petersen graph {{math|''G''(''n'', ''k'')}} is [[Vertex-transitive graph|vertex-transitive]] if and only if {{math|1=''n'' = 10}} and {{math|1=''k'' = 2}} or if {{math|''k''{{sup|2}} ≡ ±1 (mod ''n'')}} and is [[Edge-transitive graph|edge-transitive]] only in the following seven cases: {{math|1=(''n'', ''k'') = (4, 1)}}, {{math|(5, 2)}}, {{math|(8, 3)}}, {{math|(10, 2)}}, {{math|(10, 3)}}, {{math|(12, 5)}}, {{math|(24, 5)}}.<ref>{{citation
 | author1-link = R. Frucht
 | last1 = Frucht | first1 = R.
 | last2 = Graver | first2 = J. E.
 | last3 = Watkins | first3 = M. E.
 | title = The groups of the generalized Petersen graphs
 | journal = Proceedings of the Cambridge Philosophical Society
 | volume = 70
 | issue = 2 | year = 1971 | pages = 211–218
 | doi = 10.1017/S0305004100049811| bibcode = 1971PCPS...70..211F | s2cid = 122686848 }}.</ref> So the Desargues graph is one of only seven symmetric Generalized Petersen graphs. Among these seven graphs are the [[cube|cubical graph]] {{math|''G''(4, 1)}}, the [[Petersen graph]] {{math|''G''(5, 2)}}, the [[Möbius–Kantor graph]] {{math|''G''(8, 3)}}, the [[dodecahedron|dodecahedral graph]] {{math|''G''(10, 2)}} and the [[Nauru graph]] {{math|''G''(12, 5)}}.

The [[characteristic polynomial]] of the Desargues graph is
: <math>(x-3) (x-2)^4 (x-1)^5 (x+1)^5 (x+2)^4 (x+3). \, </math>
Therefore, the Desargues graph is an [[integral graph]]: its [[Spectral graph theory|spectrum]] consists entirely of integers.

==Applications==
In [[chemistry]], the Desargues graph is known as the '''Desargues–Levi graph'''; it is used to organize systems of [[stereoisomer]]s of 5-[[ligand]] compounds. In this application, the thirty edges of the graph correspond to [[pseudorotation]]s of the ligands.<ref>{{citation
  | title = Graphs of multiple 1, 2-shifts in carbonium ions and related systems
  | last1 = Balaban | first1 = A. T. | last2 = Fǎrcaşiu | first2 = D. | last3 = Bǎnicǎ | first3 = R.
  | journal = Rev. Roum. Chim.
  | volume = 11
  | pages = 1205
  | year = 1966}}</ref><ref>{{citation
  | title = Role of pseudorotation in the stereochemistry of nucleophilic displacement reactions
  | last = Mislow | first = Kurt
  | authorlink1=Kurt Mislow
  | journal = Acc. Chem. Res.
  | year = 1970
  | volume = 3
  | issue = 10
  | pages = 321–331
  | doi = 10.1021/ar50034a001}}</ref>

==Other properties==
The Desargues graph has [[Crossing number (graph theory)|rectilinear crossing number]]&nbsp;6, and is the smallest cubic graph with that crossing number {{OEIS|id=A110507}}. It is the only known nonplanar cubic [[partial cube]].<ref>{{citation
  | last1 = Klavžar | first1 = Sandi | last2 = Lipovec | first2 = Alenka
  | title = Partial cubes as subdivision graphs and as generalized Petersen graphs
  | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
  | volume = 263
  | year = 2003
  | issue = 1–3 | pages = 157–165
  | doi = 10.1016/S0012-365X(02)00575-7| doi-access = free
  }}</ref>

The Desargues graph has [[chromatic number]] 2, [[chromatic index]] 3, radius 5, diameter 5 and [[girth (graph theory)|girth]] 6. It is also a 3-[[k-vertex-connected graph|vertex-connected]] and a 3-[[k-edge-connected graph|edge-connected]] [[Hamiltonian graph]]. It has [[book thickness]] 3 and [[queue number]] 2.<ref>Wolz, Jessica, ''Engineering Linear Layouts with SAT.'' Master Thesis, University of Tübingen, 2018</ref>

All the [[cubic graph|cubic]] [[distance-regular graph]]s are known.<ref>[[Andries Brouwer|Brouwer, A. E.]]; Cohen, A. M.; and Neumaier, A. Distance-Regular Graphs. New York: Springer-Verlag, 1989.</ref> The Desargues graph is one of the 13 such graphs.

The Desargues graph can be embedded as a self-[[Petrie dual]] [[regular map (graph theory)|regular map]] in the non-orientable manifold of genus 6, with decagonal faces.<ref>{{citation | last = McMullen | first = Peter | year = 1992 | title = The regular polyhedra of type {{math|{{{mvar|p}},3{{)}}}} with {{math|2{{mvar|p}}}} vertices | journal = Geometricae Dedicata | issn = 0046-5755 | doi = 10.1007/BF00151518 | volume = 43 | issue = 3}}</ref>

[[Erv Wilson]] used this diagram to show the combination product sets (CPS) of the 3 out of 6 set. He called this Structure the Eikosany.https://www.anaphoria.com/eikosanystructures.pdf

==Gallery==
<gallery>
Image:Desargues graph colored.svg|Desargues graph colored to highlight various cycles.
Image:Desargues graph 3color edge.svg|The [[chromatic index]] of the Desargues graph is&nbsp;3.
Image:Desargues graph 2COL.svg|The [[chromatic number]] of the Desargues graph is&nbsp;2.
</gallery>

==References==
{{Reflist}}

{{DEFAULTSORT:Desargues Graph}}
[[Category:Individual graphs]]
[[Category:Regular graphs]]