Arboricity¶
Measure a graph's edge density by the fewest acyclic forest layers needed to partition all its edges.
Core Idea¶
The arboricity \(a(G)\) of a finite undirected graph is the minimum number of acyclic forest layers whose edge sets partition all its edges. Nash–Williams' theorem gives an equivalent local-density test: \(a(G)=\left\lceil\max_{|X|\ge2}|E(G[X])|/(|X|-1)\right\rceil\) for a graph with an edge. The maximum ranges over every vertex subset, not merely the whole graph; the ceiling converts the densest fractional ratio to the integer number of layers. Edgeless graphs can use zero layers by convention.[ref-61751e460019][ref-c3715d481a03]
This is a graph invariant, not just a decomposition algorithm. Relabeling vertices does not change the minimum. A proposed \(k\)-layer decomposition gives an upper bound; a subset with more than \((k-1)(|X|-1)\) edges proves that \(k-1\) layers are impossible. The theorem bridges these views by showing that the local bounds are also sufficient for a global forest partition.[^ref-61751e460019]
Scope of Application¶
All simple planar graphs have \(a\le3\): every induced subgraph remains planar and satisfies the required edge bound, with two-vertex subsets checked separately. This is only an upper bound; planar \(K_4\) has \(a=2\). For arbitrary connected graphs, Chiba and Nishizeki's particular triangle-listing algorithm runs in \(O(a(G)m)\) time with linear space, and their paper says computing \(a(G)\) or an optimal forest partition is not required by that implementation. This does not imply all subgraph-listing problems share that bound.[ref-c3715d481a03][ref-a5f84625d74b]
The finite undirected graph and acyclic edge partition are constitutive. Requiring star forests, allowing cycles, or switching to directed branching changes the invariant. Isolated vertices do not increase a nonempty graph's arboricity. An ordinary loop cannot belong to a forest, so the conventional simple or loopless graph scope should be stated.[^ref-61751e460019]
Clarity¶
The local maximum matters. A dense core plus many isolated vertices can have a low global \(m/(n-1)\) but high arboricity: the dense core still forces its layers. Arboricity is not degeneracy, which uses a vertex-peeling order; for nonempty finite simple graphs \(a(G)\le d(G)\le2a(G)-1\), so the values are related but not synonyms. It also differs from treewidth, planar thickness and edge covering number, each of which changes the allowed decomposition or covering target.[^ref-a5f84625d74b]
Manages Complexity¶
Instead of cataloging every cycle and potential edge partition, the invariant gives one integer plus a dual proof strategy: exhibit forest layers for an upper bound and locate a densest subset for a lower bound. A forest can have a high-degree hub yet \(a=1\), showing that arboricity captures a different notion of sparsity from maximum degree. The compression loses the particular optimal partition and density witness, which must be supplied separately if a task needs them.[ref-61751e460019][ref-c3715d481a03]
Abstract Reasoning¶
Fix the graph convention; for each \(X\) with at least two vertices, compare \(|E(G[X])|\) to \(k(|X|-1)\). If any subset exceeds it, \(k\) forests are impossible. If all satisfy it, Nash–Williams guarantees a partition into \(k\) forests. For \(K_4\), the largest ratio is \(6/3=2\), so \(a=2\). For nonplanar \(K_6\), it is \(15/5=3\), so \(a=3\). The proposed DAG parent is live Graph Invariant: minimum forest count is an isomorphism-preserved numerical assignment, while degeneracy is a neighboring invariant, not its genus.[ref-61751e460019][ref-a5f84625d74b]
Knowledge Transfer¶
The same roles—finite graph, acyclic edge layers, minimum count and worst induced-subgraph density—map from planar graph-class proofs to general-graph triangle-listing analysis. In the former, planarity bounds \(a\) by three; in the latter, the original algorithm uses \(a\) as a runtime parameter without needing an explicit decomposition. The method of finding a local bottleneck before trusting a global average is broadly recognizable, but the named invariant requires graph edges, forests and the \(|X|-1\) capacity rule; it is not automatically a domain-neutral prime.[ref-c3715d481a03][ref-61751e460019]
[^ref-61751e460019]: Christian Reiher and Lisa Sauermann, “Nash-Williams' Theorem on Decomposing Graphs into Forests”, original author preprint (2017), PDF pp.1–2. [^ref-c3715d481a03]: Norishige Chiba and Takao Nishizeki, “Arboricity and Subgraph Listing Algorithms”, SIAM Journal on Computing 14(1), 1985, pp.210–223. [^ref-a5f84625d74b]: Leonid Barenboim and Michael Elkin, Distributed Graph Coloring, original author-hosted monograph (2013), §§2.2–2.3.
Relationships to Other Abstractions¶
Current abstraction Arboricity Domain-specific
Parents (1) — more general patterns this builds on
-
Arboricity is a kind of Graph Invariant Domain-specific
Arboricity is a numerical graph invariant whose assignment rule minimizes acyclic edge layers.
Hierarchy path (1) — routes to 1 parentless root
- Arboricity → Graph Invariant
Neighborhood in Abstraction Space¶
Arboricity sits in a moderately populated region (56th percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.
Family — Graph Structures & Combinatorial Objects (44 abstractions)
Nearest neighbors
- Tree (Graph Theory) — 0.87
- Even-hole-free graph — 0.86
- Connected Dominating Set — 0.86
- Graph Toughness — 0.85
- Hadwiger number — 0.85
Computed from structural-signature embeddings · 2026-10-08