The algebraic connectivity of a graph is its smallest nontrivial Laplacian eigenvalue. Equivalently, it is the minimum of edge sums over all functions normalized by and . Here are vertex/edge sets, and means the difference of the values of at the vertices of the edge .

It is clear from the definition that adding edges to cannot make smaller; thus, among all graphs on vertices the maximal value of is attained by the complete graph, for which . For any other graph which can be shown as follows. Pick two non-adjacent vertices and and let , , and elsewhere. This function is normalized as required above, and its edge sum is at most since there are at most edges with a nonzero contribution.

What if we require the graph to have degree vertex at most , and look for maximal connectivity then? First of all, only connected graphs are under consideration, since for non-connected graphs. Also, only the cases are of interest, otherwise the complete graph wins. The argument in the previous paragraph shows that but is this bound attained?

The case is boring: the only two connected graphs are the path and the cycle . The cycle wins with versus .

When , one might suspect a pattern based on the following winners:

The structure of these two is the same: place points on a circle, connect each of them to nearest neighbors.

But this pattern does not continue: the 8-vertex winner is completely different.

This is simply the complete bipartite graph . And it makes sense that the “4 neighbors” graph loses when the number of vertices is large: there is too much “redundancy” among its edges, many of which connect the vertices that were already connected by short paths.

In general, when , the complete bipartite graph achieves and therefore maximizes the algebraic connectivity. The fact that follows by considering graph complement, as discussed in Laplacian spectrum of small graphs. The complement of is the disjoint union of two copies of the complete graph , for which the maximal eigenvalue is . Hence .

When is odd, we have a natural candidate in for which the argument from the previous paragraph shows . This is indeed a winner when :

The winner is not unique since one can add another edge between two of the vertices of degree 2. This does not change the , however: there is a fundamental eigenfunction that has equal values at the vertices of that added edge.

Same for : the complete bipartite graph shares the maximum value of algebraic connectivity with two other graphs formed by adding edges to it:

However, the family does not win the case in general: we already saw a 4-regular graph on 7 vertices with , beating . Perhaps wins when is odd?

I do not have any other patterns to conjecture, but here are two winners for : the cube and the “twisted cube”.

The cube is twisted by replacing a pair of edges on the top face with the diagonals. This is still a 3-regular graph and the algebraic connectivity stays the same, but it is no longer bipartite: a 5-cycle appears.