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
.
Normalized Laplacian
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.
provided
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:
as
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.