Adding an edge to a connected graph (between two of its existing vertices) makes the graph “even more” connected. How to quantify this? The Poincaré inequality gives a way to do this: for any function with zero mean,
where the sum on the left is over the vertex set , the sum on the right is over the edge set , and on the right are the endpoints of an edge. Suppose is the smallest possible constant in this inequality, the Poincaré constant of the graph. Adding an edge to the graph does not change the sum on the left but may increase the sum on the right. Thus, the new Poincaré constant satisfies : greater connectivity means smaller Poincaré constant.
It is more convenient to work with the reciprocal of , especially because , the smallest positive eigenvalue of the graph Laplacian. Let be the corresponding eigenvalue after an edge is added. The above shows that . But there is also an upper bound on how much this eigenvalue (or any Laplacian eigenvalue) can grow. Indeed, adding an edge amounts to adding the matrix
(with a bunch of zero rows/columns)
to the Laplacian matrix . The eigenvalues of are and . As a consequence of the Courant-Fischer minimax formulas, the ordered eigenvalues satisfy for every .
Both of the above bounds are sharp. If an diagonal edge is added to the 4-cycle,
the smallest positive eigenvalue remains the same (). The reason is that a typical eigenfunction for takes on values (in cyclic order) and adding an edge between two vertices with the same value of such eigenfunction does not affect the Poincaré constant.
On the other hand, adding one more edge increases from to .
Another form of the Poincaré inequality involves the vertex degree: when summing over vertices, we give each of them weight equal to the number of neighbors.
Here , the smallest positive eigenvalue of the normalized Laplacian , the matrix with on the diagonal, where off-diagonal entries are if , and otherwise. The sum of the normalized Laplacian eigenvalues is equal to (the number of vertices), regardless of how many edges are there. So we cannot expect all them to grow when an edge is added. But how do they change?
Let be the corresponding eigenvalue after an edge is added.
Here are two examples for which :
Completing a 3-path to a 3-cycle increases the eigenvalue from 1 to 3/2.
Completing a 4-path to a 4-cycle increases the eigenvalue from 1/2 to 1.
This pattern does not continue: “5-path to 5-cycle” results in a smaller increase, which is not even largest among 5-vertex graphs. It appears that the above examples are the only two cases of , with all other graphs having . (I do not have a proof of this.)
The opposite direction
Adding an edge can also make smaller (thus, the weighted Poincaré constant becomes larger, showing that it may not be as useful for quantifying the connectivity of a graph). The smallest example is adding an edge to the star graph on 4 vertices:
here but .
Let us analyze the star graphs on vertices, for general . In an earlier post we saw that , so it remains to find . Let us order the vertices so that is the center of the star and is the added edge. Write for brevity. Then the normalized Laplacian matrix is
where all rows numbered consist of in the first column and in the th column. This shows that has rank , hence is an eigenvalue of multiplicity . Also, is a simple eigenvalue as for any connected graph. Less obviously, is an eigenvalue with the corresponding eigenvector – this eigenvalue comes from the submatrix in row/columns 2 and 3, where the surrounding values in these row/columns are nice enough to cancel out. We are left with two eigenvalues to find, and we know their sum is . This means the characteristic polynomial of is of the form
where the constant remains to be found. I am going to skip to the answer here: . The quadratic formula delivers the last two eigenvalues:
The smaller of these is that we were looking for:
Thus, adding an edge to a star graph results in negative which decreases to as . Exhaustive search for shows that the star graph has the smallest value of among all graphs on vertices. It is reasonable to expect this pattern to continue, which would imply in all cases.