Laves graph
In geometry and crystallography, the Laves graph is an infinite periodic graph. Its vertices and edges consist of points and line segments in three-dimensional Euclidean space, with integer coordinates for the points. As a graph, it is cubic, meaning that exactly three edges touch each vertex, and a symmetric graph, meaning that every arc (oriented edge) can be taken to every other arc by a symmetry of the graph. As a three-dimensional geometric structure, it has chiral symmetry. The same graph can also be defined more abstractly as a covering graph of the complete graph on  four vertices. Constructions. From the integer grid. As describes, the vertices of the Laves graph can be defined by selecting one out of every eight points in the three-dimensional integer lattice, and forming their nearest neighbor graph. Specifically, one chooses the points and all the other points that can be formed by adding multiples of four to these coordinates. The edges of the Laves graph connect pairs of points whose Euclidean distance from each other is the square root of two, formula_3 (these pairs differ by one unit in two coordinates, and are the same in the third coordinate ). The other non-adjacent pairs of vertices are farther apart, at a distance of at least formula_4 from each other. The edges of the resulting geometric graph are diagonals of a subset of the faces of the regular skew polyhedron with six square faces per vertex, so the Laves graph is embedded in this skew polyhedron. It is possible to interleave two copies of the structure, filling one-fourth of the points of the integer lattice, while preserving the fact that the adjacent vertices are exactly the pairs of points that are formula_3 units apart, and all other pairs of  points are farther apart. The two copies are mirror images of each other. As a covering graph. As an abstract graph, the Laves graph can be constructed as the maximal abelian covering graph of the complete graph formula_6. Being a covering graph of formula_6 means that there is a mathematical subgroup of symmetries of the Laves graph such that, when vertices that are symmetric to each other in this subgroup are collected together into orbits of the subgroup, there are four orbits, and each pair of orbits is connected by edges of the graph to each other one. More intuitively , this means that the vertices of the Laves graph can be colored with four colors so that each vertex has neighbors of the other three colors and so that there are color-preserving symmetries taking any vertex to any other vertex with the same color. Being an abelian covering graph means that these symmetries commute with each other, forming an abelian group. In this case, it is the group formula_8 formed by addition of three-dimensional integer vectors. Finally, being a maximal abelian covering graph means that there is no other covering graph of formula_6 involving a higher-dimensional abelian  group. This construction justifies one of the alternative names of the Laves graph, the formula_6 crystal. One way to construct a maximal abelian covering graph from a smaller graph formula_11 (in this case formula_6) is to choose a spanning tree of formula_11, let formula_14 be the number of edges that are not in the spanning tree (in this case, three non-tree edges), and to choose a distinct unit vector in formula_15 for each of these non-tree edges. Then, fix the set of vertices of the covering graph to be the ordered pairs formula_16 where formula_17 is a vertex  of formula_11 and formula_19 is a vector in formula_15. For each such pair, and each edge formula_21 adjacent to formula_17 in formula_11, make an edge from formula_24 to formula_25 where formula_26 is zero if formula_21 belongs to the spanning tree and is otherwise the basis vector associated with formula_21, and where the plus or minus sign is chosen according to the direction the edge is traversed. The resulting graph is independent of the choice of the spanning tree, and the same construction can also be interpreted more abstractly using the theory of homology. Using the same construction, the hexagonal tiling  of the plane is the maximal abelian covering graph of the three-edge dipole graph, and the diamond cubic is the maximal abelian covering graph of the four-edge dipole. The formula_14-dimensional integer lattice (with unit length edges) is the maximal abelian covering graph of a graph with one vertex and formula_14 self-loops. Properties. The Laves graph is a cubic graph (there are exactly three edges at each vertex) and a symmetric graph (every incident pair of a vertex and an edge can be transformed into every other such pair by a symmetry of the graph). The girth  of this structure is 10 — the shortest cycles in the graph have 10 vertices — and 15 of these cycles pass through each vertex. The cells of the Voronoi diagram of this structure are heptadecahedra with 17 faces each. They are plesiohedra, polyhedra that tile space isohedrally. Experimenting with the structures formed by these polyhedra led Alan Schoen to discover the gyroid minimal surface. One of the four cubic induced subgraphs of the unit distance graph on the three-dimensional integer lattice having a girth of 10 is isomorphic to the Laves graph. Physical examples. Molecular crystals. Computations suggest that the  Laves graph can serve as the pattern for a metastable or perhaps unstable allotrope of carbon. Like graphite, each atom in the structure is bonded to three others, but in graphite adjacent atoms have the same bonding planes as each other whereas in this structure the bonding planes of adjacent atoms are twisted with respect to each other around the line formed by the bond, with a twisting angle of approximately 70.5°. The Laves graph may also give a crystal structure for boron; computations predict that this should be stable. Other chemicals that may form this structure include SrSi , and elemental nitrogen. Other. The structure of the Laves graph, and of gyroid surfaces derived from it, has also been observed experimentally in soap-water systems, and in the chitin networks of butterfly wing scales.