All cliques and independent sets on three vertices

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

|V|=3

|\mathcal P(V)|=8

\varnothing

\text{both clique and independent, size }0

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

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

\{0,1\}

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

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

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

\{0,1,2\}

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

\text{all eight subsets classified}

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

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

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

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 obligation

One missing pair refutes a clique; one edge refutes independence.

Complete extrema

One 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)