{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R176",
  "content_hash": null,
  "slug": "cubic20ising-claim-explicit-36-ground-state-graph",
  "type": "claim",
  "title": "A 3-connected cubic graph has exactly 36 ground states",
  "summary": "Its maximum cut has size 25, is attained by 36 spin assignments, and gives minimum Ising energy minus 20.",
  "relevance": "For Most antiferromagnetic ground states in a 3-connected cubic graph on twenty vertices, record cubic20ising-claim-explicit-36-ground-state-graph (“A 3-connected cubic graph has exactly 36 ground states”) records a bound, answer, status fact, or structural consequence. The record states: Its maximum cut has size 25, is attained by 36 spin assignments, and gives minimum Ising energy minus 20.",
  "relevance_source": "recorded",
  "body": "Use vertices `0123456789ABCDEFGHIJ`, with `A=10` through `J=19`, and edges\n```\n03 0E 0G 12 19 1E 26 27 35 39 48 4B 4J 57 5E\n6G 6J 7D 89 8B AC AH AI BH CD CI DF FH FJ GI\n```\nEvery vertex has degree three. Deleting any set of zero, one, or two vertices leaves the remaining graph connected, so its vertex connectivity is three.\n\nThe verifier fixes the spin at vertex 0 and checks the remaining \\(2^{19}\\) assignments. The largest cut has 25 edges and has 18 maximizers under that convention. Complementing every spin supplies a distinct partner, so the unrestricted degeneracy is 36. With 30 edges, the Ising energy is\n\\[\n\\sum_{uv\\in E}\\sigma_u\\sigma_v=30-2|\\delta(\\sigma)|,\n\\]\nand the minimum energy is \\(30-2\\cdot25=-20\\). The full cut-size histogram provides a stronger replay check than the maximum alone.",
  "status": "established",
  "evidence_grade": "reproduced",
  "scope": {
    "kind": "bounded",
    "statement": "the stated 30-edge graph on vertices 0 through 9 and A through J",
    "bounds": {
      "vertices": {
        "min": 20,
        "max": 20
      },
      "edges": {
        "min": 30,
        "max": 30
      },
      "spin_assignments": {
        "min": 1048576,
        "max": 1048576
      }
    },
    "exhaustive": true
  },
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "source_only",
    "kind": "claim",
    "citation": {
      "url": "https://arxiv.org/abs/1508.04675",
      "locator": "Exact certificate in cubic20ising-artifact-incumbent-verifier, reproduced on 2026-07-25"
    },
    "missing": [
      "source",
      "command",
      "runtime",
      "expected_output"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": "https://arxiv.org/abs/1508.04675",
    "locator": "Exact certificate in cubic20ising-artifact-incumbent-verifier, reproduced on 2026-07-25"
  },
  "relations": [
    {
      "slug": "R175",
      "title": "The certified interval is 36 through 254,658 ground states",
      "object_type": "claim",
      "relation": "supports",
      "direction": "outgoing"
    },
    {
      "slug": "R173",
      "title": "Exact spin and connectivity verifier for the 36-state graph",
      "object_type": "artifact",
      "relation": "supports",
      "direction": "incoming"
    },
    {
      "slug": "cubic-graph-twenty-ising-degeneracy",
      "title": "cubic graph twenty ising degeneracy",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}