{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R137",
  "content_hash": null,
  "slug": "cdt6-claim-elementary-leaf-lower-bound",
  "type": "claim",
  "title": "Minimal positive and maximal negative inputs require 1,327 leaves",
  "summary": "The 1,296 labeled spanning trees and 31 complete two-part graphs must reach distinct monochromatic leaves.",
  "relevance": "For Leaf complexity of six-vertex graph connectivity, record cdt6-claim-elementary-leaf-lower-bound (“Minimal positive and maximal negative inputs require 1,327 leaves”) records a bound, answer, status fact, or structural consequence. The record states: The 1,296 labeled spanning trees and 31 complete two-part graphs must reach distinct monochromatic leaves.",
  "relevance_source": "recorded",
  "body": "For any monotone Boolean function, distinct minimal positive inputs must reach distinct positive leaves. If two reached the same leaf, that leaf's forced-present coordinates would lie in their intersection and would contain a positive input smaller than one of them. The dual statement holds for distinct maximal negative inputs.\n\nThe minimal connected graphs on six labeled vertices are the spanning trees. Cayley's formula gives\n\\[\n6^{6-2}=1296.\n\\]\nThe maximal disconnected graphs are obtained by splitting the vertex set into two nonempty parts and including every edge within each part. Complementary parts define the same graph, so their number is\n\\[\n\\frac{2^6-2}{2}=31.\n\\]\nPositive and negative leaves are separate. Every correct tree therefore has at least \\(1296+31=1327\\) leaves. This gives a short independent check below the exact computer-certified value 1,693.",
  "status": "established",
  "evidence_grade": "reproduced",
  "scope": {
    "kind": "bounded",
    "statement": "connectivity of every simple graph on six labeled vertices in the deterministic edge-query model",
    "bounds": {
      "vertices": {
        "min": 6,
        "max": 6
      }
    },
    "exhaustive": true
  },
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "source_only",
    "kind": "claim",
    "citation": {
      "url": "https://doi.org/10.1145/3564246.3585199",
      "locator": "Self-contained minterm and maxterm count recorded 2026-07-24"
    },
    "missing": [
      "source",
      "command",
      "runtime",
      "expected_output"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": "https://doi.org/10.1145/3564246.3585199",
    "locator": "Self-contained minterm and maxterm count recorded 2026-07-24"
  },
  "relations": [
    {
      "slug": "R138",
      "title": "The minimum decision-tree leaf count is 1,693",
      "object_type": "claim",
      "relation": "supports",
      "direction": "outgoing"
    },
    {
      "slug": "connectivity-decision-tree-six-leaves",
      "title": "connectivity decision tree six leaves",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}