{"id":"graph-clique-check","version":"1.0.0","description":"Check that listed nodes form a clique (optionally maximal, of a minimum size); returns the first missing edge.","supported_operations":["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"],"unsupported_operations":["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"],"semantics":["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."],"limits":{"max_nodes":256,"max_edges":4096,"max_node_id_bytes":64,"max_clique_items":256},"pricing":{"status":"unpriced","charge_usd":null},"input_schema":{"type":"object","additionalProperties":false,"required":["nodes","edges","clique"],"properties":{"nodes":{"type":"array","maxItems":256,"items":{"type":"string","minLength":1}},"edges":{"type":"array","maxItems":4096,"items":{"type":"array","minItems":2,"maxItems":2,"items":{"type":"string","minLength":1}}},"clique":{"type":"array","maxItems":256,"items":{"type":"string","minLength":1}},"min_size":{"type":"integer","minimum":0,"maximum":256},"require_maximal":{"type":"boolean"}}},"output_schema":{"type":"object","additionalProperties":false,"required":["valid","reason","first_discrepancy","node_count","edge_count","clique_size","chromatic_lower_bound","reference_version"],"properties":{"valid":{"type":"boolean"},"reason":{"type":["string","null"],"enum":["unknown_node","duplicate_member","missing_edge","clique_too_small","not_maximal",null]},"first_discrepancy":{"type":["object","null"],"additionalProperties":false,"properties":{"node":{"type":"string"},"node_index":{"type":"integer","minimum":0},"position":{"type":"integer","minimum":0},"first_position":{"type":"integer","minimum":0},"nodes":{"type":"array","minItems":2,"maxItems":2,"items":{"type":"string"}},"positions":{"type":"array","minItems":2,"maxItems":2,"items":{"type":"integer","minimum":0}},"clique_size":{"type":"integer","minimum":0},"min_size":{"type":"integer","minimum":0}}},"node_count":{"type":"integer","minimum":0},"edge_count":{"type":"integer","minimum":0},"clique_size":{"type":"integer","minimum":0},"chromatic_lower_bound":{"type":["integer","null"],"minimum":0},"reference_version":{"type":"string","const":"diestel-gtm173-5e-2017"}}},"examples":[{"input":{"nodes":["a","b","c","d"],"edges":[["a","b"],["a","c"],["b","c"],["c","d"]],"clique":["a","b","c"],"require_maximal":true},"output":{"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"}},{"input":{"nodes":["a","b","c","d"],"edges":[["a","b"],["a","c"],["b","c"],["c","d"]],"clique":["a","c","d"]},"output":{"valid":false,"reason":"missing_edge","first_discrepancy":{"nodes":["a","d"],"positions":[0,2]},"node_count":4,"edge_count":4,"clique_size":3,"chromatic_lower_bound":null,"reference_version":"diestel-gtm173-5e-2017"}}],"execute_url":"/v1/tools/graph-clique-check/versions/1.0.0/execute"}