There are several different ways of constructing the Desargues graph:
It is the generalized Petersen graphG. 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 Desargue 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 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 bipartite Kneser graphH5,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 and can be constructed from the LCF notation: 5. As Erdős conjectured that for k positive, the subgraph of the 2k+1-dimensional hypercube induced by the vertices of weight k and k+1 is Hamiltonian, the Hamiltonicity of the Desargues graph is no surprise.
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 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 G is vertex-transitive if and only ifn = 10 and k = 2 or if k2 ≡ ±1 and is edge-transitive only in the following seven cases: = , , , , , , . So the Desargues graph is one of only seven symmetric Generalized Petersen graphs. Among these seven graphs are the cubical graphG, the Petersen graph G, the Möbius–Kantor graphG, the dodecahedral graphG and the Nauru graphG. The characteristic polynomial of the Desargues graph is Therefore, the Desargues graph is an integral graph: its 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 stereoisomers of 5-ligand compounds. In this application, the thirty edges of the graph correspond to pseudorotations of the ligands.
