{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R139",
  "content_hash": null,
  "slug": "cdt6-claim-literature-status",
  "type": "claim",
  "title": "Classical graph-property results concern depth rather than this six-vertex leaf count",
  "summary": "The edge-query model is classical, while the exact value 1,693 was not located in the published sources searched.",
  "relevance": "For Leaf complexity of six-vertex graph connectivity, record cdt6-claim-literature-status (“Classical graph-property results concern depth rather than this six-vertex leaf count”) records a bound, answer, status fact, or structural consequence. The record states: The edge-query model is classical, while the exact value 1,693 was not located in the published sources searched.",
  "relevance_source": "recorded",
  "body": "Rivest and Vuillemin study graph properties through adaptive adjacency queries and prove a quadratic worst-case query lower bound for every nontrivial monotone graph property. Kahn, Saks, and Sturtevant develop the topological evasiveness method and prove the prime-power vertex case of the evasiveness conjecture. Those results measure maximum root-to-leaf depth.\n\nChattopadhyay, Dahiya, Mande, Radhakrishnan, and Sanyal define deterministic decision-tree size as the minimum number of leaves and study it for general Boolean functions. Their subcube viewpoint matches the finite recurrence used here. A search of these sources and related graph-property literature found no tabulation of the six-vertex connectivity leaf minimum. The value 1,693 is therefore supported here by a complete finite certificate.",
  "status": "reported",
  "evidence_grade": "sourced",
  "scope": {
    "kind": "bounded",
    "statement": "graph-property decision-tree and Boolean decision-tree size literature reviewed through 2026-07-24",
    "bounds": {
      "review_year": {
        "max": 2026
      }
    },
    "exhaustive": false
  },
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "source_only",
    "kind": "claim",
    "citation": {
      "url": "https://doi.org/10.1145/3564246.3585199",
      "locator": "Literature search completed 2026-07-24; Chattopadhyay et al. 2023, Definition 2.6 and Proposition 2.12; Rivest and Vuillemin 1976; Kahn, Saks, and Sturtevant 1984"
    },
    "missing": [
      "source",
      "command",
      "runtime",
      "expected_output"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": "https://doi.org/10.1145/3564246.3585199",
    "locator": "Literature search completed 2026-07-24; Chattopadhyay et al. 2023, Definition 2.6 and Proposition 2.12; Rivest and Vuillemin 1976; Kahn, Saks, and Sturtevant 1984"
  },
  "relations": [
    {
      "slug": "R138",
      "title": "The minimum decision-tree leaf count is 1,693",
      "object_type": "claim",
      "relation": "contextualizes",
      "direction": "outgoing"
    },
    {
      "slug": "connectivity-decision-tree-six-leaves",
      "title": "connectivity decision tree six leaves",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}