# All-cut tree assurance and rounding research toolkit

Edition: 9 October 2026 Australia/Brisbane. Decision: **Prototype exact finite cut audit; defer the literal constructor**. Buyer value and profitable delivery remain hypotheses.

## Research finding

Family 174 claims a deterministic polynomial-bit constructor of a `C/k`-thin spanning tree in every finite loopless k-edge-connected multigraph, including binary multiplicities. A separate corollary gives simultaneous all-cut and nonnegative-cost rounding for rational fractional cut inputs. The construction uses hierarchy geometry, exact rational separation, frame normalization and matrix signing. Selected formal statements cover the existence and algorithmic thin-tree claims; the full fractional cost corollary is not stated in that family scope. The existence proof's compactness/fixed-point choice is distinct from the finite-bit algorithm. Family 089's planar/bounded-treewidth metric embeddings remain a separate conditional input, with no new review or arbitrary-graph extension here.

## Problem and buyer

A graph-optimization researcher or solver team needs to check whether a proposed tree meets an all-cut fraction, rather than infer it from a few familiar cuts. It also needs to know whether compressed multiplicities, chosen costs and downstream routing objectives actually match the mathematical model. A funded graph-algorithm integration or assurance module is a more plausible initial buyer hypothesis than general network-design SaaS.

## What the finding could enable

A practically redesigned constructor could provide deterministic thin-tree and cost/cut rounding modules for optimization research. The implemented bounded audit now reports exact connectivity, worst all-cut ratio, an attaining witness and the achieved `k*alpha` constant for a supplied tree. It exposes a concrete fundamental-cut checking error and handles large integer multiplicities without expanding copies. This is a finite reference for constructor validation, not a polynomial source constructor.

## Technical and commercial limits

The signing estimate explicitly permits `Cs=2^20`. Its declared cut factor is `1/2+3Cs*r^(-1/8)`, which certifies strict contraction only when `r>(6Cs)^8`, a 55-digit packing parameter. This is an algebraic condition on a conservative estimate, not a measured runtime, final theorem constant, input-size lower bound or impossibility for another algorithm. The absolute iteration cutoff `R0` and final `C` are unspecified numerically; below the cutoff the stated explicit routine returns any spanning tree. No practical constructive advantage has been shown.

The finite audit caps 16 vertices, 256-bit positive multiplicities and five million cut-edge examinations. It exhausts all nontrivial cuts up to complements, so its cost is exponential in vertex count. Partial scanning cannot certify the all-cut guarantee. Integer multiplicities count distinct edge copies; arbitrary traffic capacities are a different model. Thinness alone supplies neither route-load bounds nor latency, capacity planning or redundancy. A tree can disconnect after one edge failure. Cost rounding needs nonnegative rational data and the all-cut fractional promise.

## Minimal architecture

Binary-multiplicity graph and candidate tree -> support/tree validity -> exact bounded all-cut scan -> witness and actual ratio -> separate constructor/cost benchmark -> solver-specific interpretation. For larger inputs, an independently assessed separation/certificate method is required. Keep metric embeddings and routing objectives separate from thinness. Preserve the proposed constant, completeness status and original edge-copy interpretation.

## Existing alternatives and differentiation

Existing minimum-spanning-tree and network-optimization methods are practical baselines. A smaller or cheaper tree already preserves connectivity; the extra value needs a measured all-cut or downstream benefit. On K4, a path tree has actual thinness `3/4`, whereas its fundamental tree-cut ratios are at most `1/3`. An assurance report catches a claimed `1/3` guarantee that those cuts alone would miss. This is a mathematical verification gap, not evidence of a customer's existing error.

## Monetization hypothesis

Hypothesis: AUD 5,000–15,000 for a bounded solver/rounding validation integration. At an assumed AUD 8,000 fee and 35 specialist hours at AUD 180/hour, AUD 1,700 remains before support and overhead; 50 hours exceed the fee. A full source-constructor implementation could require substantial R&D and is not priced by that pilot. The cut-audit module overlaps the graph/evidence platform and should not be counted as another independent subscriber.

## Validation experiment

Thirty saved checks cover all 16 labeled K4 spanning trees against closed-form star/path ratios, an exact target boundary, parallel-copy scaling, a two-vertex graph with `2^100` copies, malformed/invalid trees and incomplete scan semantics. The K4 path fails target `1/3` despite passing every fundamental tree cut; its worst witness crosses three tree edges out of four original edges. Next compare supplied standard trees on a public small graph and evaluate whether a complete witness changes a solver decision. No source constructor or downstream operational improvement is demonstrated.

## Conditions to reject or defer

Defer the literal constructor while constants/cutoffs and finite workload costs are unresolved. Reject an all-cut certificate based only on partial or fundamental-cut checks. Reject commercial network claims when the required capacities, reliability or route objective lacks a separate bridge. Metric guarantees remain restricted to their source graph class. A valid actual ratio may be useful even when the universal theorem constant is commercially uninformative.

## Next concrete action

Run [audit_tree_thinness.py](../../tools/audit_tree_thinness.py) on the [K4 path fixture](../../fixtures/k4-path-thinness-2026-10-09-v1.json). Use it to validate a small baseline tree and record costs separately. Extract a fully numerical hierarchy cutoff and signing implementation only if a plausible solver workload warrants the R&D effort.

## Pinned evidence

- [Constructive introduction](https://github.com/openai/math/blob/fd4aeeb2ee4fc729c18d98444fed42fd0529eeeb/preprints/A-polynomial-time-construction-of-strong-thin-trees-September-23-2026/build/source/sections/introduction.tex), [iteration/binary reduction](https://github.com/openai/math/blob/fd4aeeb2ee4fc729c18d98444fed42fd0529eeeb/preprints/A-polynomial-time-construction-of-strong-thin-trees-September-23-2026/build/source/sections/iteration.tex), [fractional cost/cut rounding](https://github.com/openai/math/blob/fd4aeeb2ee4fc729c18d98444fed42fd0529eeeb/preprints/A-polynomial-time-construction-of-strong-thin-trees-September-23-2026/build/source/sections/fractional_rounding.tex), [selected signing constant](https://github.com/openai/math/blob/fd4aeeb2ee4fc729c18d98444fed42fd0529eeeb/preprints/A-polynomial-time-construction-of-strong-thin-trees-September-23-2026/build/source/sections/signing.tex).
- [Selected formal scope](https://github.com/openai/math/blob/fd4aeeb2ee4fc729c18d98444fed42fd0529eeeb/lean/docs/174.md); no independent kernel check.
- [Saved ratios and declared parameter calculation](../../snapshots/2026-10-08-baseline/tree-thinness-examples-2026-10-09-v1.json), [30 checks](../../snapshots/2026-10-08-baseline/tree-thinness-validation-2026-10-09-v1.json).
- Family 089: [earlier source/application record](../../snapshots/2026-10-08-baseline/families/089/source.json), reviewed separately from these all-cut claims.