Abstract
It is easy to assume that a network is robust if every vertex has many edges. This paper counts, over all small graphs, the number of vertices needed to cut, the number of edges needed to cut, and the minimum degree, side by side. No new theorem or law is claimed.
First, the three are usually equal: of the $26704$ labelled connected graphs on $6$ vertices, $25924$ have all three equal, a share of $\mathbf{0.970791}$ (Section 2).
Second, when they differ, minimum degree is the largest: vertex connectivity $\le$ edge connectivity $\le$ minimum degree holds for all, and minimum degree exceeds vertex connectivity in $780$, a share of $\mathbf{0.029209}$ (Section 2).
Third, and this is the core. Every vertex may have three edges, yet removing one vertex can cut the graph: on $8$ vertices, joining two complete graphs on four vertices by two edges from the same vertex gives vertex connectivity $1$, edge connectivity $2$ and minimum degree $3$ (Section 3).
Fourth, on $6$ vertices no graph separates them that far: vertex connectivity $<$ edge connectivity occurs in $690$ and edge connectivity $<$ minimum degree in $90$, but both strict in $0$ (Section 2).
Fifth, cut sizes equal the numbers of paths: recomputing both connectivities as the maximum number of paths sharing no vertex or no edge (maximum flow) agreed with the cut values for $2131$ graphs (Section 2).
Sixth, the separator is whether robustness is measured by minimum degree or by cuts: minimum degree looks only around one vertex; a cut looks for the thinnest place in the whole network. The former is only an upper bound on the latter (Section 4).
Keywords: vertex connectivity, edge connectivity, minimum degree, Whitney’s inequality, Menger’s theorem, cut.
Scope (what is not claimed)
No new theorem or law is claimed: vertex connectivity $\le$ edge connectivity $\le$ minimum degree (Whitney’s inequality), and connectivity equal to the number of paths sharing no vertex or no edge (Menger’s theorem), are both known. No theorem is proved: we only count all graphs on $6$ vertices and check a constructed example. Size is not generalised: graphs on $7$ or more vertices were not all counted. No design advice is given: how real communication or road networks should be built is not stated. Relation to earlier papers: Paper 838 showed that what throttles a flow is not the thin edge but the thin cut. This paper stands beside it. There edge cuts and flow were counted. Here vertex cuts, edge cuts and minimum degree are set side by side, counting that minimum degree is only an upper bound on the cuts. What is added is counting all triples over the $26704$ connected graphs on $6$ vertices, measuring the share $0.970791$ where all three are equal, building the $(1,2,3)$ example on $8$ vertices, and placing the separator on minimum degree versus cuts.
1. Notation and the Question
Setting: for a connected graph $G$, three quantities are taken. Vertex connectivity $\kappa$ is the fewest vertices whose removal disconnects the rest, edge connectivity $\lambda$ the fewest edges whose removal disconnects the graph, and minimum degree $\delta$ the smallest number of edges at a vertex.
$$\kappa(G)\le\lambda(G)\le\delta(G),\qquad \lambda(G)=\min_{\emptyset\ne S\subsetneq V}\bigl|E(S,V\setminus S)\bigr|$$All $32768$ labelled graphs on $6$ vertices were generated, and the three were counted for the connected ones. Vertex connectivity was found by trying every vertex subset; graphs that no removal disconnects, such as complete graphs, were given $n-1$.
Question: if every vertex has many edges, is the network hard to cut?
2. Counting All Graphs on $6$ Vertices
Computation 2.1: for the $26704$ connected graphs, the number with each triple was counted.
| (vertex conn., edge conn., min. degree) | count |
|---|---|
| $(1,1,1)$ | $14646$ |
| $(1,1,2)$ | $90$ |
| $(1,2,2)$ | $600$ |
| $(2,2,2)$ | $9510$ |
| $(2,3,3)$ | $90$ |
| $(3,3,3)$ | $1692$ |
| $(4,4,4)$ | $75$ |
| $(5,5,5)$ | $1$ |
Observation 2.2 the three are usually equal, and when they differ minimum degree is the largest. All three are equal in $25924$ ($0.970791$), and vertex connectivity $\le$ edge connectivity $\le$ minimum degree held for all: minimum degree exceeds vertex connectivity in $780$ ($0.029209$), vertex connectivity $<$ edge connectivity in $690$ ($0.025839$), edge connectivity $<$ minimum degree in $90$ ($0.003370$), and both strict in $0$.
Observation 2.3 cut sizes equal the numbers of paths. Both connectivities found by trying all cuts were recomputed as the maximum number of paths sharing no vertex or no edge (maximum flow with capacity $1$): for $2131$ randomly chosen graphs, both agreed.
3. A Graph with Many Edges That One Vertex Cuts
Computation 3.1: on $8$ vertices, two complete graphs on four vertices (vertices $0$ to $3$ and $4$ to $7$) were joined by two edges.
| joining | (vertex conn., edge conn., min. degree) |
|---|---|
| two edges from different vertices ($0$--$4$ and $1$--$5$) | $(2,2,3)$ |
| two edges from the same vertex ($0$--$4$ and $0$--$5$) | $(1,2,3)$ |
Observation 3.2 this is the core. Every vertex may have three edges, yet removing one vertex can cut the graph. With both edges leaving the same vertex, removing that vertex alone separates the two blocks: cutting by edges needs two, and every vertex has at least three edges, so all three values differ: $(1,2,3)$. On $6$ vertices no such graph occurred.
4. The Separator
Observation 4.1 the separator is whether robustness is measured by minimum degree or by cuts. Minimum degree looks only around a single vertex: a cut looks for the thinnest place in the whole network. A network thick around every vertex can still have a thin neck somewhere, and it is cut there. Minimum degree is only an upper bound on the cuts.
Observation 4.2 placed beside Paper 838. 838 showed that what throttles a flow is not the thin edge but the thin cut. There edge cuts set the flow. Here the same cuts are counted in two ways, by vertices and by edges, and set beside minimum degree. Both stand on the same side: not local thickness, but the cut of the whole.
Observation 4.3 what is not said. Proofs of the theorems, full counts for $7$ or more vertices, and the design of real networks are not treated. What is shown is that a large minimum degree can coexist with a small cut.
5. Census and Closing
- vertex conn. $\le$ edge conn. $\le$ min. degree (Section 1): Whitney’s inequality.
- $26704$ connected graphs (Computation 2.1): all on $6$ vertices.
- all three equal: $\mathbf{0.970791}$ (Observation 2.2): usually equal.
- minimum degree larger: $\mathbf{0.029209}$ (Observation 2.2): $780$ graphs.
- vertex conn. $<$ edge conn.: $690$ (Observation 2.2): cutting by vertices is cheaper.
- edge conn. $<$ min. degree: $90$ (Observation 2.2): a thin edge cut.
- both strict: $0$ (Observation 2.2): none on $6$ vertices.
- $(1,2,3)$ on $8$ vertices (Computation 3.1): the core.
- cuts match path counts (Observation 2.3): Menger’s theorem; $2131$ graphs.
- minimum degree, or cuts (Observation 4.1): the separator; Paper 838.
Closing: Every vertex may have three edges, yet removing one vertex can cut the graph. Among the $26704$ connected graphs on $6$ vertices, vertex connectivity, edge connectivity and minimum degree are all equal in a share of $0.970791$, and when they differ, minimum degree is the largest, because minimum degree looks only around one vertex and misses the thin neck of the whole network. On $8$ vertices, joining two complete graphs on four vertices by two edges from the same vertex gives $(1,2,3)$: every vertex has at least three edges, yet removing that one vertex cuts the graph: on $6$ vertices, no graph had both inequalities strict. Placed among the earlier papers: beside Paper 838’s “not the thin edge but the thin cut”, we set vertex cuts, edge cuts and minimum degree side by side. To be honest: full counts go only up to $6$ vertices, and the theorems are used as known and only checked.
References
- Bollobás, B. (1998). Modern Graph Theory. Springer.
- Whitney, H. (1932). Congruent Graphs and the Connectivity of Graphs. American Journal of Mathematics.
- Yamagishi, Y. (2026). What Throttles a Flow Is Not the Thin Edge but the Thin Cut [Paper 838]. YOI: https://www.yamagishiyuuki.com/yoi/838; DOI: 10.5281/zenodo.23015618
Reference
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
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 868. This paper is a preprint and has not been peer reviewed.