# All cliques and independent sets on three vertices

[← Guide index](https://ocme.evemisslab.com/en/derivations/) · [Original MKO](https://ocme.evemisslab.com/en/mko/mko-clique-and-independent-set/)

This is an owner-adopted natural-language teaching guide. Finite/arithmetic checks are not universal proofs; no Lean was run, and review scope is recorded per revision. Original source status labels are retained as historical data. Formulas retain exact TeX; no new semantic AST is invented.

derivation-mko-clique-and-independent-set-01 · ocme-new142-reader-adoption-20261021



## Goal and scope

Classify all2³ subsets to obtain omega and alpha.

Exact extrema only for the fully specified small graph.





## Givens and symbols


- work


- G1 — V={0,1,2}, E={01};2 is isolated.


- V,E — complete vertex and edge sets
- ω,α — clique and independence numbers





## Rules and sources


- mko_definition · cited — 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. · mko-clique-and-independent-set
- work · prerequisite — A finite simple undirected graph has loop-free duplicate-free unordered edges; graph properties are audited on all declared V and E. All distinct pairs in a clique are adjacent; all distinct pairs in an independent set are nonadjacent; omega and alpha are their maximum cardinalities, while maximal means no vertex can be added.





## Main derivation

S01 · impliesBefore

|V|=3

After

|\mathcal P(V)|=8

Conditions: none

Rule: work · Uses: G1, work

Leaf basis: work

There are eight vertex subsets in total.



S02 · impliesBefore

\varnothing

After

\text{both clique and independent, size }0

Conditions: none

Rule: work · Uses: G1, S01, work

Leaf basis: work

With no pairs, both universal conditions are vacuously true.



S03 · impliesBefore

\{0\},\{1\},\{2\}

After

\text{all both clique and independent, size }1

Conditions: none

Rule: work · Uses: G1, S02, work

Leaf basis: work

All three singletons have no distinct-vertex pairs.



S04 · impliesBefore

\{0,1\}

After

01\in E\implies\text{clique, not independent}

Conditions: none

Rule: work · Uses: G1, S03, work

Leaf basis: work

This pair supplies a size-two clique.



S05 · impliesBefore

\{0,2\},\{1,2\}

After

02,12\notin E\implies\text{independent, not clique}

Conditions: none

Rule: work · Uses: G1, S04, work

Leaf basis: work

The other two pairs supply size-two independent sets.



S06 · impliesBefore

\{0,1,2\}

After

02\notin E\implies\text{not clique};\quad01\in E\implies\text{not independent}

Conditions: none

Rule: work · Uses: G1, S05, work

Leaf basis: work

A missing edge and an existing edge separately refute the two properties on the triple.



S07 · impliesBefore

\text{all eight subsets classified}

After

\omega(G)=2,\quad\alpha(G)=2

Conditions: none

Rule: work · Uses: G1, S06, work

Leaf basis: work

No triple qualifies while size-two witnesses do, giving both exact extrema.



S08 · impliesBefore

\{2\}\text{ clique, no vertex addable}

After

\{2\}\text{ maximal but not maximum since }1<2

Conditions: none

Rule: work · Uses: G1, S07, work

Leaf basis: work

The isolated singleton cannot be extended as a clique but is smaller than the size-two clique.







## Substeps and lemmas

No substeps in this guide.





## Reverse audits


- S08 · premise_audit · G1, S07, work — A clique generally gives chi≥omega, not a theorem of equality.
- S07 · premise_audit · G1, S06, work — The maximum clique is{0,1}; maximum independent sets are{0,2},{1,2}.
- S06 · premise_audit · G1, S05, work — The two refutations use different pairs and must not be conflated.
- S05 · premise_audit · G1, S04, work — Both pairs are checked, not sampled.
- S04 · premise_audit · G1, S03, work — Its existing edge refutes independence of the pair.
- S03 · premise_audit · G1, S02, work — Singleton2 is a maximal clique but need not be maximum.
- S02 · premise_audit · G1, S01, work — Retain the empty set under this convention.
- S01 · premise_audit · G1, work — Cliques require every pair adjacent; independent sets require every pair nonadjacent.





## Error controls and negative controls

Pair obligationOne missing pair refutes a clique; one edge refutes independence.

Complete extremaOne empty, three singletons, three pairs and one triple total eight.


- {2} is maximal, hence maximum. → reject — {0,1} is a larger clique.
- {0,1,2} is independent. → reject — It contains edge 01.
- Omega=2 generally implies chi=2. → reject — A five-cycle has omega2 but, being odd, needs three colors.





## Result and limitations

Omega=alpha=2;{2} illustrates maximal versus maximum.







## Verification and source binding

2 declared checks for this guide; only the listed expressions are covered.


- source commit: b1b2f1dcf8c50d67a93fe52d95f8eef7b3abba9f
- adopted source SHA-256: ab2452783bc37c6ebfe68daeeaecab2d6cb9f42304f01f7d929a83e3d7698922
- original source SHA-256: b12b9f7e4aa7773c8a1042f9d5b03d1d5d69b4be8c23c84776ee6696a0aeb755
- Lean: NOT_RUN · independent AI: SCOPED_LEAD_AND_BILINGUAL_CONTEXT_REVIEW

[Same-source full JSON (formulas, ASTs, controls and revision log)](https://ocme.evemisslab.com/data/derivations/coverage-20261021/guides/derivation-mko-clique-and-independent-set-01.json)