Mathematics Graph Invariants From Config Dim Graph Invariant

Five invariants, one certificate

Graph invariants are properties of a graph that stay the same no matter how you draw it. The chromatic number, the fewest colors needed to color vertices so neighbors differ, is one. The clique number, the size of the largest set of mutually connected vertices, is another. The independence number, the largest set of vertices with no edges between them, joins them, along with the genus, the smallest number of holes a surface needs to hold the graph without crossings, and treewidth, a measure of how close a graph is to a tree. These five are the classic complexity measures of undirected graphs, each capturing a different structural feature.

In Recognition Science, the framework's machine-checked library of formal statements declares an inductive type named GraphInvariant with exactly these five constructors: chromaticNumber, cliqueNumber, independenceNumber, genus, and treewidth. The declaration also establishes a result, graphInvariant_count, that the number of these invariants is five. A structure called GraphInvariantsCert bundles that count as a certificate, and a definition graphInvariantsCert produces the certificate from that result. The whole file carries no unproved assumptions and no axioms beyond the standard logical ones; every claim is checked by the machine.

What the declaration does not claim is just as important. It does not say these five are the only possible graph invariants in mathematics; it says the framework's formal type has five members. It does not define what chromatic number or treewidth means; those definitions live elsewhere in mathematics. It does not compute any invariant for any particular graph, and it does not assert that the five are independent, complete, or ordered by difficulty. The certificate only records the count, not any property of the invariants themselves.

The practical consequence is a small, clean foundation stone. Anyone building on the framework can rely on a machine-checked fact: there are exactly five named invariants in this type, no more and no fewer. That frees later work from re-checking the count, and it gives a fixed vocabulary for talking about graph complexity within the framework. The declaration is a definitional choice, not a discovery about graphs; its value is the certainty it provides, not a new result about graph structure.

inductive GraphInvariant where
  | chromaticNumber
  | cliqueNumber
  | independenceNumber
  | genus
  | treewidth
  deriving DecidableEq, Repr, BEq, Fintype

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

structure GraphInvariantsCert where
  five_invariants : Fintype.card GraphInvariant = 5

def graphInvariantsCert : GraphInvariantsCert where
  five_invariants := graphInvariant_count

What this page does not claim

The declaration does not claim these five are the only graph invariants in all of mathematics. It does not define the invariants or compute them for any graph. It does not assert the five are independent, complete, or ordered by difficulty.

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: