Yamagishi Complexity Torus LabYamagishi Lab
Mathematical physics

[Paper 880] The Second Laplacian Eigenvalue Never Exceeds the Vertex Connectivity and Tells Apart Thin Necks Cut by the Same Number

Abstract

It is easy to assume that a network’s robustness is measured by how many vertices must be removed to cut it. This paper also measures robustness by Laplacian eigenvalues and counts, over all graphs on $6$ vertices, how it compares with the vertex cut size. No new theorem or law is claimed.

First, zero eigenvalues count components: in all $32768$ graphs on $6$ vertices, the number of zero eigenvalues matched the number of components counted by following edges (Section 2).

Second, the second eigenvalue never exceeds the vertex cut size: in all $26703$ connected graphs other than the complete graph, second eigenvalue $\le$ vertex connectivity, with equality in $3111$, a share of $\mathbf{0.116504}$ (Section 3).

Third, and this is the core. Among graphs cut by the same number of vertices, the second eigenvalue tells apart thin necks: among the $15336$ graphs cut by one vertex, it ranges from $\mathbf{0.267949}$ for the path to $1.000000$ for the star, averaging $\mathbf{0.696682}$ (Section 3).

Fourth, on $6$ vertices, the eigenvalue stayed within one below the connectivity: connectivity $2$ gives $1$ to $2$, $3$ gives $2$ to $3$, all of connectivity $4$ give $4$, and the complete graph $6$; for connectivity $1$ to $3$ it always lay between one less than the connectivity and the connectivity (Section 3).

Fifth, the path’s value matches the formula: the second eigenvalue of the path on $6$ vertices matched $2(1-\cos(\pi/6))$ within $10^{-9}$ (Section 3).

Sixth, the separator is whether one asks about vertex connectivity, counted as an integer, or the second eigenvalue, measured as a continuous value: connectivity answers only how many vertices cut the graph; the eigenvalue also answers how thin the region around the cut is (Section 4).

Keywords: graph Laplacian, algebraic connectivity, vertex connectivity, eigenvalue, Fiedler’s inequality.

Scope (what is not claimed)

No new theorem or law is claimed: that the number of zero Laplacian eigenvalues equals the number of components, that the second eigenvalue (algebraic connectivity) does not exceed vertex connectivity except for complete graphs (Fiedler’s inequality), and the formula for the path’s eigenvalues, are all known. No theorem is proved: we only count and check over all graphs on $6$ vertices. Size is not generalised: “lies between one less than the connectivity and the connectivity” was seen on $6$ vertices and is not claimed for larger graphs. Algorithms are not entered: methods for partitioning graphs by eigenvalues are not entered. Relation to earlier papers: Paper 868 showed that every vertex may have three edges, yet removing one vertex can cut the graph. This paper stands beside it. There vertex cuts, edge cuts and minimum degree were set side by side. Here the second eigenvalue is added, counting differences among graphs cut by the same number of vertices. What is added is matching zero eigenvalues with components over all graphs, measuring the share $0.116504$ where the second eigenvalue equals connectivity, laying out the spread of eigenvalues by connectivity, and placing the separator on integer connectivity versus the continuous eigenvalue.

1. Notation and the Question

Setting: for a graph on $n$ vertices, let $D$ be the diagonal matrix of degrees and $A$ the matrix with $1$ for adjacent vertices; the eigenvalues of the Laplacian $L=D-A$ are ordered as $0=\lambda_1\le\lambda_2\le\dots\le\lambda_n$.

$$L=D-A,\qquad \#\{i:\lambda_i=0\}=\text{number of components},\qquad \lambda_2\le\kappa\quad(\text{non-complete})$$

$\kappa$ is the vertex connectivity, the fewest vertices whose removal disconnects the rest. Eigenvalues were computed for all $32768$ labelled graphs on $6$ vertices; components were counted by following edges and connectivity by trying all vertex subsets.

Question: how does robustness measured by eigenvalues differ from the vertex cut size?

2. Zero Eigenvalues and Components

Computation 2.1: in all graphs, the number of eigenvalues with absolute value below $10^{-9}$ was compared with the number of components.

Observation 2.2　zero eigenvalues count components. The two matched in all $32768$: the $26704$ connected graphs have a single zero eigenvalue. A second eigenvalue above $0$ marks being connected.

3. The Second Eigenvalue and Vertex Connectivity

Computation 3.1: connected graphs were sorted by vertex connectivity, and the minimum, maximum and mean of the second eigenvalue computed.

connectivitygraphsminmaxmean
$1$$15336$$0.267949$$1.000000$$0.696682$
$2$$9600$$1.000000$$2.000000$$1.509210$
$3$$1692$$2.000000$$3.000000$$2.562857$
$4$$75$$4.000000$$4.000000$$4.000000$
$5$ (complete)$1$$6.000000$$6.000000$$6.000000$

Observation 3.2　the second eigenvalue never exceeds the vertex cut size. In all $26703$ non-complete connected graphs $\lambda_2\le\kappa$, with exact equality in $3111$, a share of $0.116504$: only the complete graph has $\lambda_2=6$, above its connectivity of $5$.

Observation 3.3　this is the core. Among graphs cut by the same number of vertices, the second eigenvalue tells apart thin necks. Among the $15336$ graphs cut by one vertex, it ranges from $0.267949$ to $1.000000$: the minimum is the path in a single line, whose value matched $2(1-\cos(\pi/6))$ within $10^{-9}$. The maximum is the star, all joined to one vertex, at $1.000000$. Both are cut by one vertex, but the path leaves a long neck wherever it is cut, while the star is thin nowhere unless its centre is removed.

Observation 3.4　on $6$ vertices, the eigenvalue stayed within one below the connectivity. Every graph with connectivity $1$ to $3$ had its second eigenvalue between one less than the connectivity and the connectivity: the $75$ graphs with connectivity $4$ all had $4.000000$. This was seen on $6$ vertices and is not claimed for larger graphs.

4. The Separator

Observation 4.1　the separator is whether one asks about vertex connectivity, counted as an integer, or the second eigenvalue, measured as a continuous value. Connectivity answers, as an integer, only how many vertices cut the graph: the second eigenvalue answers, as a continuous value, how thin the region around the cut is, and never exceeds connectivity from above. It separates the path and the star, both cut by $1$ vertex, as $0.267949$ and $1.000000$.

Observation 4.2　placed beside Paper 868. 868 set vertex cuts, edge cuts and minimum degree side by side, showing that minimum degree is only an upper bound on cuts. Here the second eigenvalue is added below that row. Minimum degree from above and the eigenvalue from below bracket the vertex cut size.

Observation 4.3　what is not said. Proofs of the theorems, graphs on $7$ or more vertices, and partitioning methods using eigenvalues are not treated. What is shown is that the second eigenvalue does not exceed the vertex cut size and separates graphs cut by the same number by how thin they are.

5. Census and Closing

  1. $L=D-A$ (Section 1): the Laplacian.
  2. zero eigenvalues $=$ components (Observation 2.2): all $32768$.
  3. $\lambda_2\le\kappa$ (Observation 3.2): all $26703$ non-complete.
  4. equality in $\mathbf{0.116504}$ (Observation 3.2): $3111$ graphs.
  5. cut by one vertex, yet $\mathbf{0.267949}$ to $1.000000$ (Computation 3.1): the core.
  6. mean $\mathbf{0.696682}$ (Computation 3.1): connectivity $1$.
  7. path is $2(1-\cos(\pi/6))$ (Observation 3.3): matches the formula.
  8. $1$ to $2$ at connectivity $2$, $2$ to $3$ at $3$ (Computation 3.1): within one below.
  9. complete graph is $6$ (Observation 3.2): the only one above its connectivity.
  10. integer, or continuous (Observation 4.1): the separator; Paper 868.

Closing: The second Laplacian eigenvalue never exceeds the vertex cut size, and tells apart thin necks among graphs cut by the same number. In all $26703$ non-complete connected graphs on $6$ vertices it was at most the vertex connectivity, and even among graphs cut by one vertex it ranges from $0.267949$ for the path to $1.000000$ for the star, because connectivity answers only how many vertices cut the graph, as an integer, while the eigenvalue also answers how thin the region around the cut is, as a continuous value. The number of zero eigenvalues matched the number of components in all $32768$ graphs, and on $6$ vertices the second eigenvalue stayed within one below the connectivity: minimum degree from above and the eigenvalue from below bracket the vertex cut size. Placed among the earlier papers: beside the vertices, edges and minimum degree set out in Paper 868, we placed the second eigenvalue bracketing from below. To be honest: only graphs on $6$ vertices were counted, and the theorems were used as known and only checked.

References

  1. Chung, F. R. K. (1997). Spectral Graph Theory. American Mathematical Society.
  2. Fiedler, M. (1973). Algebraic Connectivity of Graphs. Czechoslovak Mathematical Journal.
  3. Yamagishi, Y. (2026). Every Vertex May Have Three Edges, Yet Removing One Vertex Can Cut the Graph [Paper 868]. YOI: https://www.yamagishiyuuki.com/yoi/868

Reference

Yamagishi, Y. (2026). The Second Laplacian Eigenvalue Never Exceeds the Vertex Connectivity and Tells Apart Thin Necks Cut by the Same Number [Paper 880]. YOI: https://www.yamagishiyuuki.com/yoi/880
ORCID: 0009-0006-8587-3450

PDF (English) · PDF (Japanese) · Date proof of the English PDF (OpenTimestamps .ots) · SHA256SUMS

The record page for this paper (in Japanese, with the PDFs in each language and the date proof): YOI 880. This paper is a preprint and has not been peer reviewed.