# Minimum spanning tree certificate check

`minimum-spanning-tree-certificate-check` · version 1.0.0 · Numbers & math · free, no key needed

Check a claimed minimum spanning tree: structure, exact weight, then the cycle/cut optimality test with a swap witness

**Use when you need to: verify minimum spanning tree · check mst optimality · is this the minimum spanning tree.**

## Decide before calling

Read the [versioned contract](/v1/tools/minimum-spanning-tree-certificate-check/versions/1.0.0) and the supported scope below. Reuse `minimum-spanning-tree-certificate-check@1.0.0` when your input, required output and limits match it. Choose another approach for an unsupported operation.

## Explain the choice

"I can use `minimum-spanning-tree-certificate-check@1.0.0` for verify minimum spanning tree. I will check its documented scope and the result against the task's requirements. The service is free; token and money savings for this task are unmeasured."

## Supported

- verify minimum spanning tree
- check mst optimality
- is this the minimum spanning tree
- mst cycle property check
- mst cut property certificate
- find cheaper swap for spanning tree
- validate kruskal or prim result

## Not supported

- computing a minimum spanning tree from scratch
- minimum spanning forests of disconnected graphs
- directed minimum arborescences (Chu-Liu/Edmonds)
- bottleneck or degree-constrained spanning trees

## Behavior

- Order: structural stage (missing_edge, duplicate_edge, cycle_edge with a cycle witness, disconnected) in tree_edge_ids order; then, when claimed_weight is not null, the exact tree weight must equal it (weight_mismatch); then the cycle condition over non-tree edges in graph.edges order.
- Cycle condition: for every non-tree edge e = {u, v} with u != v, w(e) must be at least the heaviest weight on the unique tree path from u to v; the first failure is cycle_property_violated with index = position in graph.edges, expected = heaviest tree-path weight, actual = w(e), witness_edge_ids = the tree path from u to v.
- The condition holds for all non-tree edges exactly when the tree is a minimum spanning tree (cycle property, equivalently each tree edge is light for its fundamental cut, CLRS Theorem 21.1). Swapping e for the first heaviest witness edge lowers the weight. Ties are allowed, so every alternative minimum tree passes.
- claimed_weight is a canonical integer string of at most 40 digits or null (no weight claim); tree_weight is the computed sum when the structure is valid, otherwise null. Arithmetic is exact.
- Undirected edges {id, u, v, weight}; parallel edges and self-loops allowed (non-tree self-loops never violate the condition); IDs compared code unit for code unit. Graph errors throw invalid_input; size limits throw limit_exceeded first.
- Reference: CLRS 4th ed. (2022) chapter 21; reference_version "clrs-4e-2022-ch21-minimum-spanning-trees".

## Input

- `graph` (object, required)
- `tree_edge_ids` (array of string, required): max items 2000; each min length 1; each max length 64
- `claimed_weight` (string or null, required): pattern `^(0|-?[1-9][0-9]*)$`

## Output

- `valid` (boolean, required)
- `reason` (one of null, "missing_edge", "duplicate_edge", "cycle_edge", "disconnected", "weight_mismatch", "cycle_property_violated", required)
- `first_discrepancy` (object or null, required)
- `tree_weight` (string or null, required): pattern `^(0|-?[1-9][0-9]*)$`
- `reference_version` (constant "clrs-4e-2022-ch21-minimum-spanning-trees", required)

## Limits

- max vertices: 500
- max edges: 2000
- max tree edges: 2000
- max id bytes: 64
- max integer digits: 40

## Example

Request input:

```json
{
  "graph": {
    "vertices": [
      "a",
      "b",
      "c",
      "d"
    ],
    "edges": [
      {
        "id": "ab",
        "u": "a",
        "v": "b",
        "weight": "1"
      },
      {
        "id": "bc",
        "u": "b",
        "v": "c",
        "weight": "2"
      },
      {
        "id": "cd",
        "u": "c",
        "v": "d",
        "weight": "3"
      },
      {
        "id": "da",
        "u": "d",
        "v": "a",
        "weight": "4"
      },
      {
        "id": "ac",
        "u": "a",
        "v": "c",
        "weight": "5"
      }
    ]
  },
  "tree_edge_ids": [
    "ab",
    "bc",
    "cd"
  ],
  "claimed_weight": "6"
}
```

Response:

```json
{
  "result": {
    "valid": true,
    "reason": null,
    "first_discrepancy": null,
    "tree_weight": "6",
    "reference_version": "clrs-4e-2022-ch21-minimum-spanning-trees"
  }
}
```

## How to call it

### MCP

Connect `https://computefirst.net/mcp` ([setup](/docs#connect)), then call `execute` with:

```json
{
  "id": "minimum-spanning-tree-certificate-check",
  "version": "1.0.0",
  "input": {
    "graph": {
      "vertices": [
        "a",
        "b",
        "c",
        "d"
      ],
      "edges": [
        {
          "id": "ab",
          "u": "a",
          "v": "b",
          "weight": "1"
        },
        {
          "id": "bc",
          "u": "b",
          "v": "c",
          "weight": "2"
        },
        {
          "id": "cd",
          "u": "c",
          "v": "d",
          "weight": "3"
        },
        {
          "id": "da",
          "u": "d",
          "v": "a",
          "weight": "4"
        },
        {
          "id": "ac",
          "u": "a",
          "v": "c",
          "weight": "5"
        }
      ]
    },
    "tree_edge_ids": [
      "ab",
      "bc",
      "cd"
    ],
    "claimed_weight": "6"
  }
}
```

### HTTP (no key)

```sh
curl -X POST https://computefirst.net/v1/tools/minimum-spanning-tree-certificate-check/versions/1.0.0/execute \
  -H "Content-Type: application/json" \
  -d '{"graph":{"vertices":["a","b","c","d"],"edges":[{"id":"ab","u":"a","v":"b","weight":"1"},{"id":"bc","u":"b","v":"c","weight":"2"},{"id":"cd","u":"c","v":"d","weight":"3"},{"id":"da","u":"d","v":"a","weight":"4"},{"id":"ac","u":"a","v":"c","weight":"5"}]},"tree_edge_ids":["ab","bc","cd"],"claimed_weight":"6"}'
```

The machine-readable contract is at [/v1/tools/minimum-spanning-tree-certificate-check/versions/1.0.0](/v1/tools/minimum-spanning-tree-certificate-check/versions/1.0.0).

### CLI

```sh
node cli.mjs run minimum-spanning-tree-certificate-check 1.0.0 --input input.json --base-url https://computefirst.net
```

Get the client at [/clients/cli/](/clients/cli/).

## Related tools

- [Maximum flow certificate check](/tools/maximum-flow-certificate-check): Check a claimed max flow with a min-cut certificate or residual search; reports the first failure or augmenting path.
- [Network cut capacity check](/tools/network-cut-capacity-check): Check a claimed s-t cut: source-side membership, the edges crossing it and its capacity, with exact integers.
- [Chi square decomposition check](/tools/chi-square-decomposition-check): Check a claimed Pearson chi-square, its per-cell (O-E)^2/E terms and df exactly; returns the first wrong term.
- [Chromatic certificate check](/tools/chromatic-certificate-check): Check a claim chi(G) = k: a proper k-colouring plus a clique or bounded exhaustive proof; returns the first discrepancy.
- [Graph coloring check](/tools/graph-coloring-check): Check that a node colouring of an undirected graph is proper (and within k colours); returns the first conflict.
- [Lp optimality certificate check](/tools/lp-optimality-certificate-check): Check an LP optimum claim from a primal x and dual y: feasibility, complementary slackness and zero duality gap.