Mathematics Graph Invariants From Config Dim Graph Invariants Cert

A certificate for five graph invariants

In graph theory, an invariant is a number that does not change when you relabel the vertices. The chromatic number, the fewest colors needed so adjacent vertices differ, is one. The clique number, the size of the largest set of mutually connected vertices, is another. The independence number, the largest set with no edges between them, the genus, the minimum number of handles a surface needs to embed the graph without crossings, and the treewidth, a measure of how close a graph is to a tree, complete a standard list of five.

These five invariants each capture a different kind of computational difficulty. Coloring, finding cliques, and finding independent sets are all classic hard problems. Genus and treewidth describe structural complexity from different angles. Together they give a rough but useful profile of how complex a graph is. This is the classical surface a reader expects, and it stands on its own.

In Recognition Science, a machine-checked library of formal theorems defines a type called GraphInvariant whose members are exactly these five: chromatic number, clique number, independence number, genus, and treewidth. A theorem proves this type has exactly five elements. The declaration GraphInvariantsCert is a certificate, a packaged proof of that count. It does not compute any of the invariants for a particular graph, and it does not relate them to each other.

The certificate's content is deliberately narrow. It establishes a count, not a theory. It says nothing about how these invariants behave, which graphs achieve extreme values, or how they connect to the framework's deeper results about recognition cycles or dimensions. The five names are the whole payload.

What the certificate offers is a clean, verified anchor. Anyone building on the framework can refer to this certificate and know the five canonical invariants are a settled list, not a moving target. The count is checked by the machine, and the machine found no gaps and no extra assumptions.

theorem graphInvariant_count : Fintype.card GraphInvariant = 5 := by decide

structure GraphInvariantsCert where
  five_invariants : Fintype.card GraphInvariant = 5

What this page does not claim

The certificate does not compute any invariant for a specific graph. It does not prove relationships between the five invariants. It does not connect these invariants to the framework's recognition cycle or spatial dimension results.

Verify this page

Every tagged claim above names its theorem. To check one yourself rather than trust this page, elaborate the source module with Lean 4 and audit its axiom basis:

$ lake env lean IndisputableMonolith/Mathematics/GraphInvariantsFromConfigDim.lean
expected axiom basis: [propext, Classical.choice, Quot.sound] (the Lean kernel's standard three; no RS-specific axioms)

A page whose claims cannot be reproduced this way does not ship. In production, every anchor links to the exact declaration in the public source release, and this block carries the build receipt for the page itself.

Derived articles

This page is generated by a question-recursion engine: the questions its answers raise become the next pages. The current agenda, with open targets marked red: