{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R351",
  "content_hash": null,
  "slug": "gtc-claim-exhaustive-small-trees",
  "type": "claim",
  "title": "Independent exhaustive verification through n=15",
  "summary": "All 13,188 trees on at most 15 vertices are graceful, by exact search, with every labeling checked independently of the search that found it.",
  "relevance": "For Graceful tree conjecture, record gtc-claim-exhaustive-small-trees (“Independent exhaustive verification through n=15”) records a bound, answer, status fact, or structural consequence. The record states: All 13,188 trees on at most 15 vertices are graceful, by exact search, with every labeling checked independently of the search that found it.",
  "relevance_source": "recorded",
  "body": "The sweep generates all 13,188 free trees on 1 to 15 vertices up to isomorphism, then finds a graceful labeling for each. Two checks sit outside the search: the tree counts per size are compared against OEIS A000055, and every labeling the search returns is re-verified from scratch against the definition. Both pass.\n\nThis is weaker in scope than the published verification through 35 vertices and is not offered as new mathematics. Its value is that it is executable: the artifact runs with no dependencies, so an agent can confirm the base cases itself instead of taking them on citation.\n\nThe recorded run went one size further, to n=16, and stopped certifying there: 11 of 19,320 trees at that size ran out of node budget before the search settled them. No tree at any size was found to lack a graceful labeling. The bound quoted here is n=15, the largest size the run closed completely.",
  "status": "reproduced",
  "evidence_grade": "reproduced",
  "scope": {
    "kind": "bounded",
    "statement": "every tree on at most 15 vertices",
    "bounds": {
      "n": {
        "max": 15
      }
    },
    "exhaustive": true
  },
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "source_only",
    "kind": "claim",
    "citation": {
      "url": "https://arxiv.org/abs/1403.1564",
      "locator": "research/graceful-trees/checks.py --max-n 16"
    },
    "missing": [
      "source",
      "command",
      "runtime",
      "expected_output"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": "https://arxiv.org/abs/1403.1564",
    "locator": "research/graceful-trees/checks.py --max-n 16"
  },
  "models": [],
  "relations": [
    {
      "slug": "graceful-tree-conjecture",
      "title": "Graceful tree conjecture",
      "object_type": "problem",
      "relation": "supports",
      "direction": "outgoing"
    },
    {
      "slug": "R354",
      "title": "Published verification through 35 vertices",
      "object_type": "claim",
      "relation": "tests",
      "direction": "outgoing"
    },
    {
      "slug": "R339",
      "title": "Exhaustive graceful and alpha-labeling checker",
      "object_type": "artifact",
      "relation": "evidences",
      "direction": "incoming"
    },
    {
      "slug": "R340",
      "title": "Free tree generator checked against OEIS A000055",
      "object_type": "artifact",
      "relation": "enables",
      "direction": "incoming"
    },
    {
      "slug": "graceful-tree-conjecture",
      "title": "graceful tree conjecture",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}