{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R553",
  "content_hash": null,
  "slug": "nonagon-tree-claim-exact-minimum",
  "type": "claim",
  "title": "The minimum nonagon tree dilation is 2+4 cos(pi/9)",
  "summary": "Every spanning tree has dilation at least 2+4 cos(pi/9), and each vertex-centered star attains equality.",
  "relevance": "For Minimum spanning-tree dilation on the regular nonagon, record nonagon-tree-claim-exact-minimum (“The minimum nonagon tree dilation is 2+4 cos(pi/9)”) records a bound, answer, status fact, or structural consequence. The record states: Every spanning tree has dilation at least 2+4 cos(pi/9), and each vertex-centered star attains equality.",
  "relevance_source": "recorded",
  "body": "Number the vertices cyclically from 0 through 8, put \\(\\theta=\\pi/9\\), and write \\(\\ell_k=2\\sin(k\\theta)\\) for a chord spanning \\(k\\) polygon steps. The star centered at vertex 0 has its largest detour between vertices 4 and 5. That path has length \\(2\\ell_4\\), while the direct chord has length \\(\\ell_1\\). Its dilation is therefore\n\\[\nS=\\frac{2\\sin(4\\pi/9)}{\\sin(\\pi/9)}.\n\\]\nThe executable certificate compares every pair in this star and finds no larger ratio.\n\nLet \\(x=2\\cos(\\pi/9)\\). The triple-angle identity gives \\(x^3-3x-1=0\\), and \\(\\sin(4\\theta)/\\sin\\theta=x^3-2x=x+1\\). Hence\n\\[\nS=2+2x=2+4\\cos(\\pi/9).\n\\]\nEquivalently, \\(S\\) is the largest root of \\(s^3-6s^2+8\\). The certified interval is\n\\[\n5.758770483142<S<5.758770483144.\n\\]\n\nPruefer words enumerate the \\(9^7=4{,}782{,}969\\) labeled spanning trees exactly once. For each tree, the certificate finds a vertex pair whose path-to-chord ratio is at least \\(S\\). Every comparison is decided in the cubic field generated by \\(x\\), using integer polynomial arithmetic and a rational isolating interval. This proves the matching lower bound. There are 7,515 labeled minimizing trees. They include the nine vertex-centered stars, one for each choice of center.",
  "status": "established",
  "evidence_grade": "reproduced",
  "scope": {
    "kind": "bounded",
    "statement": "all Euclidean spanning trees on the nine labeled vertices of a regular nonagon of circumradius one",
    "bounds": {
      "vertex_count": {
        "min": 9,
        "max": 9
      },
      "circumradius": {
        "min": 1,
        "max": 1
      },
      "labeled_tree_count": {
        "min": 4782969,
        "max": 4782969
      }
    },
    "exhaustive": true
  },
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "source_only",
    "kind": "claim",
    "citation": {
      "url": "https://doi.org/10.4230/LIPIcs.SoCG.2025.26",
      "locator": "Independent exact certificate nonagon-tree-artifact-complete-pruefer-search, executed on 2026-07-24"
    },
    "missing": [
      "source",
      "command",
      "runtime",
      "expected_output"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": "https://doi.org/10.4230/LIPIcs.SoCG.2025.26",
    "locator": "Independent exact certificate nonagon-tree-artifact-complete-pruefer-search, executed on 2026-07-24"
  },
  "relations": [
    {
      "slug": "R551",
      "title": "Exact Pruefer search over all nonagon spanning trees",
      "object_type": "artifact",
      "relation": "evidences",
      "direction": "incoming"
    },
    {
      "slug": "R552",
      "title": "Literature gives general circle bounds but no exact nonagon value",
      "object_type": "attempt",
      "relation": "informs",
      "direction": "incoming"
    },
    {
      "slug": "regular-nonagon-tree-dilation",
      "title": "regular nonagon tree dilation",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}