Connective spaces: Graphs

The simplest geometrical property is connectivity; the basic properties of connected sets are:

A graph is a connective space with a finite number of points.

[This usage of the word graph is unrelated to its meaning as the curve of a function.]

Two points that are connected together are represented by two vertices connected by an edge.

[Note: An edge is not really there; it does not consist of points: it is a symbol, drawn merely for clarity, to show that two points are connected. Similarly, the position of the vertices is not important; which vertices connect to which others is.]

Connective spaces (graphs) vary from totally disconnected to completely connected.

Let's use the graph below to illustrate some ideas about connectivity.

Connective spaces separate into distinct connected pieces, called components. This graph has three, but most have just one.

Each point may be different from the others in how it connects to them. The number of adjacent points, called the degree of the vertex, varies — here the average degree is 4 edges per vertex, but some are more well-connected (the larger vertices), some less, and one is isolated. As graphs get larger, every vertex is connected to half the other vertices, on average.

Most vertices are connected to their neighbors in different ways. But it can sometimes happen that some points are indistinguishable from each other, in the sense that transposing them gives the same graph; e.g., the smaller component has two such vertices, colored green.

A path is a connected chain of vertices.

Any two vertices in a component can be joined by a path. In fact, the path need not be longer than a certain length called the diameter of the graph. Here the diameters of the three components are, surprisingly, 0, 3, and 3. The average distance between vertices is typically quite small for a random graph, a property known as "small degrees of separation".

Sometimes, there is a path that visits every vertex. One such path is shown for the smaller component. Rarer are such paths that start and end at the same vertex (a closed path or 'cycle'): can you find one for the larger component? (Click on the edges to form a path.)

A subset of vertices and their edges is a subgraph. Example. In general, finding a specific subgraph in a larger graph is a time-consuming problem (NP).

The size of the largest completely connected subgraph gives one measure of the complexity of a graph, called its clique size. The clique size of the connected graphs above are 1,3,4. On average, the clique size grows log-slowly with the number of vertices.

Totally disconnected graphs have clique size 1.
Graphs with clique size 2 contain no "triangles", e.g.,

Try to color the above graphs in a way that adjacent vertices are colored differently, and using the least number of colors. They need respectively, 1, 3, 4, 2 (path), 2 (tree), 3 (cycle), 2 (bipartite).

The least number of colors needed is at least as big as the clique size, but it can be quite larger. On average, it is about \(\frac{1}{2}n\log_2 n\). The number of colors is more closely related to another concept: the genus of a graph.$$\color{purple}\mathit{genus} := \mathrm{Vertices} - \mathrm{Edges} + \mathrm{Cycles} - \cdots \pm \mathrm{Components}$$Only the independent cycles should be counted here.

One can find the genus by summing the genuses of each component; here the three graphs have genus of 0, 1, 0, so the total genus is 1.
Graphs with genus 0 are called planar: they can be drawn on a plane without any crossing edges; e.g., the path, cycle, and tree, but not the 3-3 bipartite graph ("the three utilities puzzle".
Graphs with genus 0, 1, 2, ... need at most 4, 7, 8, 9, 10, 11, 12, 12, ... colors (about \(3+\sqrt{12g}\)) to color adjacent vertices differently.

These are the smallest connected graphs, with 1, 2, 3, or 4 vertices. They are all planar.

One vertex

Two vertices

Three vertices

Four vertices

Five vertices

There are twenty-one connected graphs with 5 vertices. They are also planar, except for the very last one, which has genus 1.

The variety of graphs grows very fast: there are over a hundred graphs with 6 vertices, and over eight hundred with 7.

Graphs can combine as a product:

But the number of graphs that are products becomes vanishingly small as the number of vertices increases; thus almost all graphs are irreducible.

Graphs often arise as relations between objects, or as the 'skeleton' of shapes.

Symmetric Graphs

Symmetric graphs have all vertices similar to each other, that is, they are all transposable. Apart from the totally disconnected, the completely connected, the cycles, and the even complete bipartite, there are many others:

Other examples of symmetric (planar) graphs arise from the Platonic and Archimedean solids:

The sparsest graphs (with few edges, spectral radius<2) are very few — there are two infinite families and three sporadic graphs:

Infinite Graphs