# 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](/v1/tools/spanning-tree-structure-check/versions/1.0.0) 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: ```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" } ] }, "tree_edge_ids": [ "ab", "bc", "cd" ] } ``` Response: ```json { "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](/docs#connect)), then call `execute` with: ```json { "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) ```sh 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](/v1/tools/spanning-tree-structure-check/versions/1.0.0). ### CLI ```sh 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/](/clients/cli/). ## Related tools - [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. - [Directed cycle check](/tools/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](/tools/graph-clique-check): Check that listed nodes form a clique (optionally maximal, of a minimum size); returns the first missing edge. - [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. - [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. - [Bipartite coloring check](/tools/bipartite-coloring-check): Check a complete 0/1 coloring witness for graph bipartiteness and report the first certificate discrepancy.