# Cliques and independent sets

This English edition is an AI candidate and does not yet have an OCME Atlas (GPT-6) Twin closure receipt.

Every pair of distinct vertices of a clique is adjacent; every pair of an independent set is nonadjacent. Inclusion-maximal and maximum-cardinality are different.

mko-clique-and-independent-set · definition · v0.10.0



## Mathematical statement

Audit all candidate pairs. One valid size-r candidate gives only a lower bound on omega or alpha; maximum claims require the complete vertex-subset search or another global upper certificate. Maximal means no vertex can be added. Clique number bounds chromatic number below, but does not imply equality in general.





## Representative formula (exact TeX)

omega(G)





## Assumptions


- The complete finite loop-free simple undirected graph and duplicate-free candidate subset are supplied.
- Exact extrema use n≤9 and all2^n subsets.





## Symbol scope


- omega — maximum clique size
- alpha — maximum independent-set size





## Intuition, definition, and misconceptions

Cliques and independent sets check every distinct selected pair.

Maximal means locally nonextendable; maximum means globally largest cardinality.

A clique supplies a chromatic lower bound, not equality in general.

An inclusion-maximal clique need not be maximum, and omega alone does not establish chi=omega.





## Adopted derivation guide

[All cliques and independent sets on three vertices](https://ocme.evemisslab.com/en/derivations/derivation-mko-clique-and-independent-set-01/)The original MKO is retained. The guide has its own append-only revision and verification boundaries, not a new Lean proof.





## Prerequisites


- [Finite simple undirected graphs](https://ocme.evemisslab.com/en/mko/mko-graph/) — The adjacency relation is complete.
- [Subset](https://ocme.evemisslab.com/en/mko/mko-subset/) — The candidate is a vertex subset.





## Verification boundary

Global extrema certificates cover only small complete finite graphs; no efficient large-graph algorithm is claimed.

not_formalized

This does not mean the content is false; it means no replayable computational or formal evidence is registered yet.





## Next obligation

Add Ramsey bounds and perfect graphs.





## Same-source structured data

This page and the interactive view use the same object and existing language edition; this adds no proof or human review.

[Canonical MKO JSON](https://ocme.evemisslab.com/data/mko/clique-and-independent-set.json) · [Plain Markdown](https://ocme.evemisslab.com/en/mko/mko-clique-and-independent-set/index.md)