{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R349",
  "content_hash": null,
  "slug": "gtc-claim-decomposition-motivation",
  "type": "claim",
  "title": "A graceful tree decomposes the complete graph",
  "summary": "A graceful labeling of a tree with \\(m\\) edges gives a cyclic decomposition of \\(K_{2m+1}\\) into \\(2m+1\\) copies of that tree.",
  "relevance": "For Graceful tree conjecture, record gtc-claim-decomposition-motivation (“A graceful tree decomposes the complete graph”) records a bound, answer, status fact, or structural consequence. The record states: A graceful labeling of a tree with \\(m\\) edges gives a cyclic decomposition of \\(K_{2m+1}\\) into \\(2m+1\\) copies of that tree.",
  "relevance_source": "recorded",
  "body": "Rosa's original motivation. Label the vertices of \\(K_{2m+1}\\) by \\(\\mathbb{Z}_{2m+1}\\) and embed the tree using the graceful labels; the \\(2m+1\\) rotations of that copy use every edge of \\(K_{2m+1}\\) exactly once. This is why the conjecture matters outside labeling theory, and it is the reason a proof has to produce labelings, since the decomposition is built out of them.",
  "status": "established",
  "evidence_grade": "sourced",
  "scope": {
    "kind": "universal",
    "statement": "every tree carrying a graceful labeling"
  },
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "source_only",
    "kind": "claim",
    "citation": {
      "url": "https://www.combinatorics.org/ojs/index.php/eljc/article/view/DS6",
      "locator": "Gallian, Dynamic Survey of Graph Labeling, introduction"
    },
    "missing": [
      "source",
      "command",
      "runtime",
      "expected_output"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": "https://www.combinatorics.org/ojs/index.php/eljc/article/view/DS6",
    "locator": "Gallian, Dynamic Survey of Graph Labeling, introduction"
  },
  "models": [],
  "relations": [
    {
      "slug": "graceful-tree-conjecture",
      "title": "Graceful tree conjecture",
      "object_type": "problem",
      "relation": "informs",
      "direction": "outgoing"
    },
    {
      "slug": "graceful-tree-conjecture",
      "title": "graceful tree conjecture",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}