{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R347",
  "content_hash": null,
  "slug": "gtc-claim-alpha-not-universal",
  "type": "claim",
  "title": "The smallest tree with no alpha-labeling has seven vertices",
  "summary": "The spider with three legs of length two admits a graceful labeling but no alpha-labeling, and it is the smallest tree that does not.",
  "relevance": "For Graceful tree conjecture, record gtc-claim-alpha-not-universal (“The smallest tree with no alpha-labeling has seven vertices”) records a bound, answer, status fact, or structural consequence. The record states: The spider with three legs of length two admits a graceful labeling but no alpha-labeling, and it is the smallest tree that does not.",
  "relevance_source": "recorded",
  "body": "Every tree on at most six vertices has an alpha-labeling. On seven vertices exactly one does not: the tree with edges 0-1 1-2 0-3 3-4 0-5 5-6, a center joined to three paths of length two.\n\nThe obstruction is countable by hand. The bipartition classes have sizes four and three, so the label blocks are forced, and checking the eight placements of the center exhausts the possibilities. The tree is graceful; only the bipartition-respecting form fails.",
  "status": "established",
  "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 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": [],
  "continuation": null,
  "relations": [
    {
      "slug": "R342",
      "title": "Prove the conjecture by induction through alpha-labelings",
      "object_type": "attempt",
      "relation": "constrains",
      "direction": "outgoing"
    },
    {
      "slug": "gtc-problem-alpha-characterization",
      "title": "Characterize the trees with no alpha-labeling",
      "object_type": "problem",
      "relation": "informs",
      "direction": "outgoing"
    },
    {
      "slug": "R339",
      "title": "Exhaustive graceful and alpha-labeling checker",
      "object_type": "artifact",
      "relation": "evidences",
      "direction": "incoming"
    },
    {
      "slug": "graceful-tree-conjecture",
      "title": "graceful tree conjecture",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}