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 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:

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

Response:

{
  "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), then call execute with:

{
  "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)

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.

CLI

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

Get the client at /clients/cli/.

Related 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: 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: Check a claimed s-t flow for capacity bounds and conservation with exact integers; returns the first bad edge or node.
• 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: Check that a node colouring of an undirected graph is proper (and within k colours); returns the first conflict.
• Maximum flow certificate check: Check a claimed max flow with a min-cut certificate or residual search; reports the first failure or augmenting path.