# Spanning tree weight check

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

Check that claimed edge IDs form a spanning tree and that their exact total weight equals the claimed weight.

**Use when you need to: check spanning tree total weight · verify claimed tree cost · sum weights of tree edges exactly.**

## Decide before calling

Read the [versioned contract](/v1/tools/spanning-tree-weight-check/versions/1.0.0) and the supported scope below. Reuse `spanning-tree-weight-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 `spanning-tree-weight-check@1.0.0` for check spanning tree total weight. 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

- check spanning tree total weight
- verify claimed tree cost
- sum weights of tree edges exactly
- validate spanning tree weight claim
- tree weight audit
- check cost of chosen network links

## Not supported

- minimality (use minimum-spanning-tree-certificate-check)
- decimal or floating-point weights
- weights of arbitrary non-tree edge sets

## Behavior

- Structural stage first, exactly as spanning-tree-structure-check (missing_edge, duplicate_edge, cycle_edge with a cycle witness, disconnected), in tree_edge_ids order.
- Then the exact big-integer sum of the claimed edge weights must equal claimed_weight (weight_mismatch; expected = computed sum, actual = claim).
- Weights and claimed_weight are canonical integer strings ^(0|-?[1-9][0-9]*)$ of at most 40 digits; tree_weight is the computed sum when the structure is valid, otherwise null.
- Undirected edges {id, u, v, weight}; parallel edges and self-loops allowed; IDs compared code unit for code unit.
- Graph errors throw invalid_input; counts and sizes over the limits throw limit_exceeded first.
- Reference: CLRS 4th ed. (2022) section 21.1; 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, required): pattern `^(0|-?[1-9][0-9]*)$`

## Output

- `valid` (boolean, required)
- `reason` (one of null, "missing_edge", "duplicate_edge", "cycle_edge", "disconnected", "weight_mismatch", 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": [
      "x",
      "y",
      "z"
    ],
    "edges": [
      {
        "id": "xy",
        "u": "x",
        "v": "y",
        "weight": "-2"
      },
      {
        "id": "yz",
        "u": "y",
        "v": "z",
        "weight": "15"
      },
      {
        "id": "xz",
        "u": "x",
        "v": "z",
        "weight": "40"
      }
    ]
  },
  "tree_edge_ids": [
    "xy",
    "yz"
  ],
  "claimed_weight": "13"
}
```

Response:

```json
{
  "result": {
    "valid": true,
    "reason": null,
    "first_discrepancy": null,
    "tree_weight": "13",
    "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": "spanning-tree-weight-check",
  "version": "1.0.0",
  "input": {
    "graph": {
      "vertices": [
        "x",
        "y",
        "z"
      ],
      "edges": [
        {
          "id": "xy",
          "u": "x",
          "v": "y",
          "weight": "-2"
        },
        {
          "id": "yz",
          "u": "y",
          "v": "z",
          "weight": "15"
        },
        {
          "id": "xz",
          "u": "x",
          "v": "z",
          "weight": "40"
        }
      ]
    },
    "tree_edge_ids": [
      "xy",
      "yz"
    ],
    "claimed_weight": "13"
  }
}
```

### HTTP (no key)

```sh
curl -X POST https://computefirst.net/v1/tools/spanning-tree-weight-check/versions/1.0.0/execute \
  -H "Content-Type: application/json" \
  -d '{"graph":{"vertices":["x","y","z"],"edges":[{"id":"xy","u":"x","v":"y","weight":"-2"},{"id":"yz","u":"y","v":"z","weight":"15"},{"id":"xz","u":"x","v":"z","weight":"40"}]},"tree_edge_ids":["xy","yz"],"claimed_weight":"13"}'
```

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

### CLI

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

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

## Related tools

- [Graph path weight check](/tools/graph-path-weight-check): Check that a path of edge IDs walks source to target in a weighted digraph and sums to the claimed exact weight.
- [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.
- [Coloring count check](/tools/coloring-count-check): Check a proper indexed coloring and an exact canonical-decimal claim for its number of distinct colors.
- [Sample summary check](/tools/sample-summary-check): Check claimed count, sum, mean, median, range, variance or SD of an exact sample; returns the first mismatching field.
- [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 flow feasibility check](/tools/network-flow-feasibility-check): Check a claimed s-t flow for capacity bounds and conservation with exact integers; returns the first bad edge or node.