Abstract
When the vertices of a graph are to be divided into two equal halves while cutting as few edges between them as possible, a common method divides them by the values of the second eigenvector of the Laplacian. This paper takes a graph with a thin neck, a grid, and a “ladder with a tail” whose rungs cover only the back half, and compares the number of edges cut by splitting at the median of the eigenvector with the minimum bisection found by exhaustive search. No new theorem or law is claimed.
First, for the thin neck and the grid, the eigenvector split hits the minimum: for two complete graphs on $8$ vertices joined by $2$ edges (second eigenvalue $0.417424$) it cut $2$ edges, and for the $4\times4$ grid ($0.585786$) $4$ edges, both equal to the minimum (Section 2).
Second, for the ladder with a tail, it cuts more than the minimum: with top and bottom paths of $8$ vertices each (second eigenvalue $0.103300$) it cut $4$ edges, and with $10$ each ($0.071278$) $5$ edges, while the minimum was $2$ in both cases, ratios of $\mathbf{2.000000}$ and $\mathbf{2.500000}$ (Section 2).
Third, the eigenvector split separated the top path from the bottom path: for both sizes, the two halves split at the median were exactly the top path and the bottom path, and what was cut was the rungs. The minimum bisection cuts the two paths left from right at the boundary between tail and ladder, $2$ edges (Section 3).
Fourth, before and after rounding, top-bottom and left-right swap order: the sum of squared differences divided by the sum of squares was smallest for the eigenvector itself (before rounding), $0.103300$ and $0.071278$, but rounded to two levels the top-bottom split gave $1.000000$ and the left-right split $0.500000$ and $0.400000$, the left-right being smaller (Section 3).
Fifth, the separator is whether one compares the values before rounding to two levels or the edge counts after: the eigenvector minimizes the quantity before rounding. The number of edges cut is the quantity after rounding, and the two minima need not point to the same split (Section 4).
Keywords: spectral bisection, Fiedler vector, Laplacian, minimum bisection, Rayleigh quotient, graph partitioning.
Scope (what is not claimed)
No new theorem or law is claimed: dividing a graph by the second eigenvector of the Laplacian (the Fiedler vector), its property of minimizing the quotient of squared differences, and the fact that a ladder with a tail is known as a hard case for this split (Guattery and Miller) are all known. Only small graphs are treated: only four graphs with $16$ and $20$ vertices; how the number of cut edges grows as the tail lengthens is not claimed from two sizes. Other splitting methods are not entered: thresholds other than the median, splits using several eigenvectors, flow-based splits and multi-level splits are not treated. No real network is treated: applications such as circuit layout or assigning work to processors are not discussed. Relation to earlier papers: Paper 880, in its scope note, did not enter algorithms and did not enter methods that use eigenvalues to divide a graph; this paper sits in that seat (no earlier occupant). Paper 880 showed that the second Laplacian eigenvalue never exceeds the vertex connectivity and tells apart thin necks cut by the same number. Here it is counted whether the number of edges cut hits the minimum when the graph is actually divided by the eigenvector rather than measured by the eigenvalue. What is added: comparing the eigenvector split with the exhaustive minimum on four graphs, finding that the ladder with a tail is cut at $2.000000$ and $2.500000$ times the minimum, confirming that the split separates the top path from the bottom path, listing the quotients before and after rounding, and placing the separator on “the values before rounding, or the counts after”.
1. Notation and the Question
Setting: let $L$ be the Laplacian of a graph on $n$ vertices, $\lambda_2$ its second smallest eigenvalue and $f$ the corresponding eigenvector (the Fiedler vector). With values $x_i$ on the vertices, consider the following quotient (the Rayleigh quotient).
$$R(x)=\frac{\sum_{\text{edges }uv}(x_u-x_v)^2}{\sum_i x_i^2},\qquad \lambda_2=\min_{x\perp\mathbf{1}}R(x)=R(f)$$Rounding the values to $+1$ and $-1$ with $n/2$ of each gives $R(x)=4\times(\text{edges cut})/n$. Spectral bisection divides the vertices into halves of $n/2$ at the median of $f$. This is compared with the smallest number of cut edges over all bisections, found by exhaustive search.
Graphs: (1) two complete graphs on $8$ vertices joined by $2$ edges ($16$ vertices, $58$ edges); (2) the $4\times4$ grid ($16$ vertices, $24$ edges); (3), (4) ladders with a tail: top and bottom paths of $2k$ vertices each, with only $k$ rungs on the back half ($k=4$: $16$ vertices, $18$ edges; $k=5$: $20$ vertices, $23$ edges).
Question: does splitting at the median of the eigenvector hit the minimum number of cut edges?
2. Comparing Four Graphs
Computation 2.1: the eigenvector split and the exhaustive minimum.
| graph | edges | second eigenvalue | cut by eigenvector | minimum bisection | ratio |
|---|---|---|---|---|---|
| two complete graphs joined by $2$ edges | $58$ | $0.417424$ | $2$ | $2$ | $1.000000$ |
| grid $4\times4$ | $24$ | $0.585786$ | $4$ | $4$ | $1.000000$ |
| ladder with a tail $k=4$ | $18$ | $0.103300$ | $4$ | $2$ | $\mathbf{2.000000}$ |
| ladder with a tail $k=5$ | $23$ | $0.071278$ | $5$ | $2$ | $\mathbf{2.500000}$ |
Observation 2.2 the thin neck and the grid hit the minimum, and the ladder with a tail cuts more than the minimum. For the thin neck, the eigenvector separated the two clusters and cut only the $2$ joining edges: for the ladder with a tail it cut $4$ edges at $k=4$ and $5$ at $k=5$, $2.000000$ and $2.500000$ times the minimum of $2$. At both sizes the number cut equaled $k$, but beyond that nothing was counted.
3. What Was Cut, Before and After Rounding
Computation 3.1: for the ladder with a tail, the eigenvector split and the left-right split (cutting both paths at the boundary between tail and ladder).
| $k$ | split top from bottom | edges cut left-right | $R(f)$ (before rounding) | top-bottom (rounded) | left-right (rounded) |
|---|---|---|---|---|---|
| $4$ | yes | $2$ | $0.103300$ | $1.000000$ | $0.500000$ |
| $5$ | yes | $2$ | $0.071278$ | $1.000000$ | $0.400000$ |
Observation 3.2 the eigenvector split separated the top path from the bottom path and cut the rungs. For both sizes, the two halves at the median were exactly the top path and the bottom path. There are $k$ rungs, so the number cut is $k$. The minimum bisection cuts the two paths left from right, $2$ edges.
Observation 3.3 before and after rounding, top-bottom and left-right swap order. The quotient of the eigenvector itself is $0.103300$ and $0.071278$, smaller than any two-level split: but rounded to two levels, the top-bottom split the eigenvector pointed to gives $1.000000$ and the left-right split $0.500000$ and $0.400000$, the left-right being smaller. The shape that was smallest before rounding did not point to the smallest after rounding.
4. The Separator
Observation 4.1 the separator is whether one compares the values before rounding to two levels or the edge counts after. The eigenvector minimizes the quotient when values may be placed freely: the number of cut edges equals the quotient after rounding to two levels. For the thin neck the two minima pointed to the same split; for the ladder with a tail they pointed to different splits.
Observation 4.2 what is not said. Why the eigenvector separates top from bottom, how the count grows as the tail lengthens, thresholds other than the median, other splitting methods and real networks are not treated. What is shown is that on four small graphs the eigenvector split sometimes hits the minimum and sometimes does not, and that where it does not, the order swaps between before and after rounding.
5. Roll Call and Closing
- the quotient $R$ and $\lambda_2$; the rounded quotient counts cut edges (Section 1): two minima.
- ratio $1.000000$ for the thin neck and the grid (Computation 2.1): hits the minimum.
- ratios $\mathbf{2.000000}$ and $\mathbf{2.500000}$ for the ladder with a tail (Computation 2.1): cuts more than the minimum.
- top path separated from bottom path (Computation 3.1): the rungs were cut.
- rounded: top-bottom $1.000000$, left-right $0.500000$ and $0.400000$ (Observation 3.3): the order swaps.
- before rounding, or after (Observation 4.1): the separator; the scope note of Paper 880.
Closing: Bisecting by the eigenvector hits the minimum for a thin neck but splits a ladder with a tail top from bottom. For two complete graphs on $8$ vertices joined together and for the grid, splitting at the median of the eigenvector cut the same number of edges as the minimum bisection: for the ladder with a tail it separated the top path from the bottom path and cut the rungs, $2.000000$ and $2.500000$ times the minimum. Rounded to two levels, the left-right split had the smaller quotient. The separator is whether one compares the values before rounding to two levels or the edge counts after. Placed among the earlier papers: the thinness of necks that Paper 880 told apart by the eigenvalue was counted as edges cut when the graph is actually divided by the eigenvector. To be honest: how far the split misses on large graphs, and why it separates top from bottom, are not said. Cases that hit and miss on four small graphs were set side by side, and no further.
References
- Fiedler, M. (1973). Algebraic connectivity of graphs. Czechoslovak Mathematical Journal.
- Guattery, S., & Miller, G. L. (1998). On the quality of spectral separators. SIAM Journal on Matrix Analysis and Applications.
- 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
Reference
Yamagishi, Y. (2026). Bisecting by the Eigenvector Hits the Minimum for a Thin Neck but Splits a Ladder with a Tail Top from Bottom [Paper 940]. YOI: https://www.yamagishiyuuki.com/yoi/940
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 940. This paper is a preprint and has not been peer reviewed.