# Graph clique check

`graph-clique-check` · version 1.0.0 · Numbers & math · free, no key needed

Check that listed nodes form a clique (optionally maximal, of a minimum size); returns the first missing edge.

**Use when you need to: check that nodes form a clique · validate a clique witness in a graph · are these vertices pairwise adjacent.**

## Decide before calling

Read the [versioned contract](/v1/tools/graph-clique-check/versions/1.0.0) and the supported scope below. Reuse `graph-clique-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 `graph-clique-check@1.0.0` for check that nodes form a clique. 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 that nodes form a clique
- validate a clique witness in a graph
- are these vertices pairwise adjacent
- check a maximal clique claim
- clique lower bound for chromatic number
- find the missing edge in a claimed clique
- verify a complete subgraph claim

## Not supported

- find a maximum clique or compute the clique number
- prove that no larger clique exists
- directed graphs, multigraphs or self-loops
- Unicode normalization of node ids

## Behavior

- Reference: R. Diestel, Graph Theory, 5th ed. (GTM 173, Springer 2017), section 1.1 (K^r, adjacency) and section 5.5 (clique number, chi(G) >= omega(G)); every output carries reference_version "diestel-gtm173-5e-2017".
- Graph: simple undirected; nodes lists V, edges lists pairs [u, v] (orientation ignored). duplicate_node, unknown_edge_endpoint, self_loop, duplicate_edge and empty ids are invalid_input (details.reason); nodes are scanned before edges, each in array order.
- Node ids are exact JavaScript strings: no trimming, case folding or Unicode normalization; lone surrogates are invalid_input; each id is at most 64 UTF-8 bytes.
- A clique is a list of pairwise adjacent, pairwise distinct nodes; the empty list is the empty clique. Positions are 0-based indexes into the caller's list.
- min_size (0..256) is optional; omitted means no size requirement. require_maximal is optional; omitted means false. Maximal: no node outside the clique is adjacent to every member.
- Check order: (1) per position, unknown_node {node, position} else duplicate_member {node, position, first_position}; (2) missing_edge over pairs i < j in lexicographic order {nodes, positions}; (3) clique_too_small {clique_size, min_size}; (4) not_maximal: first extending node in node order {node, node_index}.
- clique_size is the witness length. When valid, chromatic_lower_bound = clique_size (a proper colouring separates all clique members); when invalid it is null.

## Input

- `nodes` (array of string, required): max items 256; each min length 1
- `edges` (array of array of string, required): max items 4096; each min items 2; each max items 2; each each min length 1
- `clique` (array of string, required): max items 256; each min length 1
- `min_size` (integer, optional): min 0; max 256
- `require_maximal` (boolean, optional)

## Output

- `valid` (boolean, required)
- `reason` (one of "unknown_node", "duplicate_member", "missing_edge", "clique_too_small", "not_maximal", null, required)
- `first_discrepancy` (object or null, required)
- `node_count` (integer, required): min 0
- `edge_count` (integer, required): min 0
- `clique_size` (integer, required): min 0
- `chromatic_lower_bound` (integer or null, required): min 0
- `reference_version` (constant "diestel-gtm173-5e-2017", required)

## Limits

- max nodes: 256
- max edges: 4096
- max node id bytes: 64
- max clique items: 256

## Example

Request input:

```json
{
  "nodes": [
    "a",
    "b",
    "c",
    "d"
  ],
  "edges": [
    [
      "a",
      "b"
    ],
    [
      "a",
      "c"
    ],
    [
      "b",
      "c"
    ],
    [
      "c",
      "d"
    ]
  ],
  "clique": [
    "a",
    "b",
    "c"
  ],
  "require_maximal": true
}
```

Response:

```json
{
  "result": {
    "valid": true,
    "reason": null,
    "first_discrepancy": null,
    "node_count": 4,
    "edge_count": 4,
    "clique_size": 3,
    "chromatic_lower_bound": 3,
    "reference_version": "diestel-gtm173-5e-2017"
  }
}
```

## How to call it

### MCP

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

```json
{
  "id": "graph-clique-check",
  "version": "1.0.0",
  "input": {
    "nodes": [
      "a",
      "b",
      "c",
      "d"
    ],
    "edges": [
      [
        "a",
        "b"
      ],
      [
        "a",
        "c"
      ],
      [
        "b",
        "c"
      ],
      [
        "c",
        "d"
      ]
    ],
    "clique": [
      "a",
      "b",
      "c"
    ],
    "require_maximal": true
  }
}
```

### HTTP (no key)

```sh
curl -X POST https://computefirst.net/v1/tools/graph-clique-check/versions/1.0.0/execute \
  -H "Content-Type: application/json" \
  -d '{"nodes":["a","b","c","d"],"edges":[["a","b"],["a","c"],["b","c"],["c","d"]],"clique":["a","b","c"],"require_maximal":true}'
```

The machine-readable contract is at [/v1/tools/graph-clique-check/versions/1.0.0](/v1/tools/graph-clique-check/versions/1.0.0).

### CLI

```sh
node cli.mjs run graph-clique-check 1.0.0 --input input.json --base-url https://computefirst.net
```

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

## Related tools

- [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 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 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.
- [Contingency expected check](/tools/contingency-expected-check): Check claimed expected counts (row total x column total / N) of a count table exactly; returns the first wrong cell.
- [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.
- [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.