Graphs and crystal nets#

This page fixes basic graph-theoretic terminology as it is used in crystal-net topology and throughout TopoMetrics. The conventions here follow the review of crystal nets as graphs by Delgado-Friedrichs and O’Keeffe.

Vertices, edges, and neighbors#

A graph consists of a set of vertices (nodes) and a set of edges (pairs of vertices):

  • vertices typically correspond to atomic sites (or clusters of atoms),

  • edges correspond to some notion of connection (e.g., bonds or neighbours).

Unless stated otherwise, we work with undirected graphs: an edge between vertices i and j does not carry an orientation.

We usually exclude loops and multiple edges:

  • A loop is an edge from a vertex to itself.

  • Multiple edges are several distinct edges between the same two vertices.

A graph with no loops and no multiple edges is called a simple graph. Crystal nets are normally treated as simple graphs.

If two vertices are connected by an edge they are neighbours, and the set of all neighbors of a vertex is its neighbourhood. The coordination number of a vertex is the number of incident edges (i.e., the size of its neighborhood). In graph theory this is also called the vertex degree, but “degree” and “valence” already have meanings in chemistry, so we will prefer coordination number here.

A graph in which every vertex has the same coordination number n is called n-regular (or simply “regular”).

Paths, cycles, and connectivity#

A path (also called a chain) is a sequence of vertices

\[(x_1, x_2, \dots, x_n)\]

such that each consecutive pair \((x_k, x_{k+1})\) is joined by an edge. The length of the path is the number of edges it contains.

A cycle (or circuit) is a closed path that starts and ends at the same vertex:

\[(x_1, x_2, \dots, x_{n-1}, x_1).\]

We are usually interested in elementary cycles: cycles in which no edge or vertex (other than the start/end) is repeated.

A graph is connected if there is at least one path between every pair of vertices.

Removing a vertex (and all incident edges) is called deletion of that vertex. A graph is called n-connected if it has at least n + 1 vertices and deleting any set of fewer than n vertices never disconnects it.

Embeddings and planarity#

A graph is a combinatorial object: it does not come with coordinates for its vertices. Choosing coordinates and drawing edges as straight segments in Euclidean space is called an embedding (or realisation) of the graph.

An embedding is faithful if edges only meet at their endpoints: they do not cross and do not pass through other vertices.

  • A graph is planar if it admits a faithful embedding in the plane (two-dimensional space).

  • Any finite graph can be embedded faithfully in three-dimensional space.

Graph isomorphism and symmetry#

Two graphs are isomorphic if there is a one-to-one correspondence between their vertices that preserves adjacency (edges). Intuitively, they are the same graph, drawn differently.

An automorphism of a graph is an isomorphism from the graph to itself. The set of all automorphisms forms the graph group, which is a purely combinatorial notion of symmetry.