Optimal Local Decompression on Graphs of Odd Maximum Degree

This preprint answers the two-bit local-decompression question for cubic graphs posed by Balliu, Brandt, Kuhn, Nowicki, Olivetti, Rotenberg and Suomela in Distributed Computation with Local Advice (DISC 2025, Section 1.8, question 4). More generally, for every fixed odd maximum-degree bound Delta >= 3, every subset of the edges of a finite simple graph of maximum degree at most Delta can be encoded using exactly (Delta+1)/2 bits per vertex. A deterministic LOCAL decoder recovers edge membership at both endpoints in Delta^{O(Delta)} communication rounds, independently of graph order. The uniform integer bit budget is optimal by counting. The construction combines separated marker cells, positional encoding over the nonmarker alphabet, and balanced edge ownership on a residual quotient graph. One orientation-advice bit is decoded before the payload, using the published one-bit almost-balanced orientation theorem of Balliu and coauthors as an essential external input. The encoder is unrestricted. The result does not claim practical decoding constants, an efficient encoder, or a resolution of the exact even-degree budget. The deposit includes the manuscript, a clean Lean/Python supplement with pinned build and submission metadata, and a separate citation file. Lean checks finite coding and graph constructions, marker geometry, conditional reconstruction and locality, bounded packet and advice locality without marker coverage, virtual-parameter facts, and the counting lower bound. The full operational LOCAL theorem and the published orientation theorem remain written proofs; the formalization is partial. The companion includes a finite Python invariant check. The work was developed with extensive AI assistance, and independent human peer review is not claimed.