Clique
Definition
Let be a graph. A clique in is a set of vertices of such that any two distinct vertices of are adjacent.
Remarks
A set is a clique if and only if the induced subgraph on is a complete graph. A set is a clique in if and only if it is an independent set in the complement graph. To decide whether a graph has a clique of a given size is an NP-complete problem.
Where this leads
7 pages build on this one.
Further reading
About this page
| Tag | 0G52BPNPKG |
|---|---|
| URI | m2://0G52BPNPKG |
| Kind | definition |
| Writing | W1 stated |
| MSC | 05C69 |
| Defines | Clique |
Markdown · JSON · Edit on GitHub
What this page needs for W2
- edge instance_of in: one example (0 of 1)
- edge not_instance_of in: one non-example that fails one clause (0 of 1)
The writing levels say how complete the text of a page is. They do not measure its truth.