Spanning tree structure check

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

Check that claimed edge IDs form a spanning tree of a graph; reports the first missing, repeated or cyclic edge

Use when you need to: check spanning tree claim · is this edge set a spanning tree · verify tree spans all vertices.

Decide before calling

Read the versioned contract and the supported scope below. Reuse spanning-tree-structure-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-structure-check@1.0.0 for check spanning tree claim. 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 claim
• is this edge set a spanning tree
• verify tree spans all vertices
• detect cycle in claimed tree edges
• check tree edges connect every vertex
• spanning tree structure validation
• find first redundant edge in tree

Not supported

• spanning forests of disconnected graphs
• directed arborescences (rooted out-trees)
• finding a spanning tree (the caller supplies the claim)
• weight or minimality checks (see spanning-tree-weight-check and minimum-spanning-tree-certificate-check)

Behavior

• tree_edge_ids is processed in array order: each ID must exist in graph.edges (missing_edge), must not repeat (duplicate_edge, at the second occurrence) and must join two different components of the edges accepted so far (cycle_edge).
• For cycle_edge, witness_edge_ids is the cycle: the unique path of earlier claimed edges from the edge's u to its v, then the edge itself (a self-loop is the one-edge cycle).
• After the claim, every vertex must be connected to graph.vertices[0]; otherwise disconnected at the first unreached vertex in graph.vertices order, with expected = |V| - 1 and actual = claimed edge count.
• Edges are undirected {id, u, v, weight}; parallel edges and self-loops are allowed because each edge has its own ID. IDs are 1..64 UTF-8 bytes, compared code unit for code unit (no normalization).
• Graph errors (duplicate vertex or edge IDs, unknown endpoints, malformed integer weights, unknown fields) throw invalid_input; counts and sizes over the limits throw limit_exceeded first.
• Reference: CLRS 4th ed. (2022) section 21.1 and Appendix B.5.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

Output

• valid (boolean, required)
• reason (one of null, "missing_edge", "duplicate_edge", "cycle_edge", "disconnected", required)
• first_discrepancy (object or null, required)
• tree_edge_count (integer, required): min 0; max 2000
• 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:

{
  "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"
      }
    ]
  },
  "tree_edge_ids": [
    "ab",
    "bc",
    "cd"
  ]
}

Response:

{
  "result": {
    "valid": true,
    "reason": null,
    "first_discrepancy": null,
    "tree_edge_count": 3,
    "reference_version": "clrs-4e-2022-ch21-minimum-spanning-trees"
  }
}

How to call it

MCP

Connect https://computefirst.net/mcp (setup), then call execute with:

{
  "id": "spanning-tree-structure-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"
        }
      ]
    },
    "tree_edge_ids": [
      "ab",
      "bc",
      "cd"
    ]
  }
}

HTTP (no key)

curl -X POST https://computefirst.net/v1/tools/spanning-tree-structure-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"}]},"tree_edge_ids":["ab","bc","cd"]}'

The machine-readable contract is at /v1/tools/spanning-tree-structure-check/versions/1.0.0.

CLI

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

Get the client at /clients/cli/.

Related tools

• Network cut capacity check: Check a claimed s-t cut: source-side membership, the edges crossing it and its capacity, with exact integers.
• Directed cycle check: Check a claimed directed cycle (closed vertex list) in a digraph, or a no-cycle claim with a deterministic witness
• Graph clique check: Check that listed nodes form a clique (optionally maximal, of a minimum size); returns the first missing edge.
• Graph coloring check: Check that a node colouring of an undirected graph is proper (and within k colours); returns the first conflict.
• 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.
• Bipartite coloring check: Check a complete 0/1 coloring witness for graph bipartiteness and report the first certificate discrepancy.