Cliques and independent sets

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

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 — The adjacency relation is complete.
• 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.