{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R342",
  "content_hash": null,
  "slug": "gtc-attempt-alpha-induction",
  "type": "attempt",
  "title": "Prove the conjecture by induction through alpha-labelings",
  "summary": "Alpha-labelings compose, so an induction that keeps one would close the conjecture. It cannot: alpha-labelings fail to exist from seven vertices up, and the count of exceptions keeps growing.",
  "relevance": "For Graceful tree conjecture, record gtc-attempt-alpha-induction (“Prove the conjecture by induction through alpha-labelings”) documents a concrete method, search boundary, or failed route. The record states: Alpha-labelings compose, so an induction that keeps one would close the conjecture.",
  "relevance_source": "recorded",
  "body": "The route is attractive because alpha-labelings, unlike graceful labelings in general, survive the natural joins. If every tree had one, an induction on the tree order would go through, and much of the literature's composition machinery is built on exactly that property.\n\nThe route cannot be completed. The smallest counterexample is the spider with edges 0-1 1-2 0-3 3-4 0-5 5-6 on seven vertices, and the count of trees with no alpha-labeling grows from there: n=7: 1, n=8: 2, n=9: 5, n=10: 11, n=11: 22, n=12: 44, n=13: 82, n=14: 147, n=15: 254. An induction that carries an alpha-labeling as its hypothesis stops at a set of trees that keeps getting larger, so it cannot reach every tree at any size.\n\nOne qualifier, since it points at what the route is still good for. Those trees are a falling share of all trees, 10.6% at n=9 down to 3.3% at n=15, so the alpha route covers most trees at the sizes that can be counted, including every caterpillar. It is a partial method with a measured boundary, and whether that boundary thins out asymptotically is itself open.",
  "status": "failed_as_complete_proof",
  "evidence_grade": "reproduced",
  "scope": {
    "kind": "bounded",
    "statement": "tested against every tree on at most 15 vertices",
    "bounds": {
      "n": {
        "max": 15
      }
    },
    "exhaustive": true
  },
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "source_only",
    "kind": "attempt",
    "citation": {
      "url": "https://arxiv.org/abs/1403.1564",
      "locator": "research/graceful-trees/checks.py --max-n 15"
    },
    "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 15"
  },
  "models": [],
  "relations": [
    {
      "slug": "R347",
      "title": "The smallest tree with no alpha-labeling has seven vertices",
      "object_type": "claim",
      "relation": "constrains",
      "direction": "incoming"
    },
    {
      "slug": "R346",
      "title": "Trees with no alpha-labeling: the count doubles, the share peaks and falls",
      "object_type": "claim",
      "relation": "constrains",
      "direction": "incoming"
    },
    {
      "slug": "graceful-tree-conjecture",
      "title": "Graceful tree conjecture",
      "object_type": "problem",
      "relation": "attempts",
      "direction": "outgoing"
    },
    {
      "slug": "graceful-tree-conjecture",
      "title": "graceful tree conjecture",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}