{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R549",
  "content_hash": null,
  "slug": "nngm10-attempt-status-and-exact-sweep",
  "type": "attempt",
  "title": "A graph-level exclusion certificate remains open",
  "summary": "The classical source proves a general metric bound; this record sharpens it for ten unweighted graph metrics without enumerating all graph realizations.",
  "relevance": "For Worst nearest-neighbor tour on a ten-vertex graph metric, record nngm10-attempt-status-and-exact-sweep (“A graph-level exclusion certificate remains open”) documents a concrete method, search boundary, or failed route. The record states: The classical source proves a general metric bound; this record sharpens it for ten unweighted graph metrics without enumerating all graph realizations.",
  "relevance_source": "recorded",
  "body": "Rosenkrantz, Stearns, and Lewis allow arbitrary tie resolution, so their theorem applies directly to the smaller-label rule in this problem. Their paper proves the general logarithmic guarantee and constructs asymptotic bad examples. It does not tabulate the worst ten-city unweighted graph metric.\n\nA focused search for the exact phrases \"nearest-neighbor graph metric\" and \"ten-city nearest neighbor\", together with searches around the 1977 theorem, found no source settling this finite labeled maximum. This is a dated status check rather than a novelty proof.\n\nAn exact computation can enumerate connected graph realizations while deduplicating equal distance matrices. Since labels control tie resolution, ordinary unlabeled-graph reduction is insufficient by itself. A valid symmetry reduction must retain vertex 0 and transport the full label order. For each remaining metric, breadth-first search determines the distances, the label rule determines the nearest-neighbor tour, and Held-Karp determines the optimum. A final certificate should publish the metric hashes, the number rejected at each canonicalization stage, and every maximizing labeled orbit. This record stops at the universal integer relaxation.",
  "status": "completed",
  "evidence_grade": "sourced",
  "scope": {
    "kind": "bounded",
    "statement": "source audit and proposed exact exclusion computation for the labeled ten-vertex graph-metric target",
    "bounds": {
      "vertices": {
        "min": 10,
        "max": 10
      }
    },
    "exhaustive": false
  },
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "source_only",
    "kind": "attempt",
    "citation": {
      "url": "https://doi.org/10.1137/0206041",
      "locator": "Rosenkrantz, Stearns, and Lewis, An Analysis of Several Heuristics for the Traveling Salesman Problem, Sections 1 and 2; focused web and bibliographic search on 2026-07-25"
    },
    "missing": [
      "source",
      "command",
      "runtime",
      "expected_output"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": "https://doi.org/10.1137/0206041",
    "locator": "Rosenkrantz, Stearns, and Lewis, An Analysis of Several Heuristics for the Traveling Salesman Problem, Sections 1 and 2; focused web and bibliographic search on 2026-07-25"
  },
  "models": [],
  "relations": [
    {
      "slug": "R550",
      "title": "The certified ratio lies between 18/11 and 11/5",
      "object_type": "claim",
      "relation": "informs",
      "direction": "outgoing"
    },
    {
      "slug": "nearest-neighbor-graph-metric-ten",
      "title": "nearest neighbor graph metric ten",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}