Mathematics Graph Invariants From Config Dim

Five structural measures

A graph invariant is a number you can attach to a network that does not change when you redraw it. The classic examples are the chromatic number, the fewest colors needed to color the vertices so no two neighbors share a color, and the clique number, the size of the largest group of vertices that are all mutually connected. Two other standard measures are the independence number, the largest set of vertices with no edges between them, and the genus, the smallest number of holes a surface needs to hold the graph without edges crossing. The fifth is treewidth, a measure of how far a graph is from being a tree, which appears throughout algorithmic graph theory. These five are the canonical invariants a student meets in any graph theory course, and each captures a different kind of structural complexity.

The history of these invariants is long and separate. The chromatic number goes back to the four color problem, posed in 1852 by Francis Guthrie and proved only in 1976 by Kenneth Appel and Wolfgang Haken. The clique and independence numbers are tied to Ramsey theory, which asks how much order a large enough structure must contain. The genus was studied by Percy Heawood and others in the late nineteenth century as a way to draw graphs on surfaces. Treewidth was introduced in 1984 by Neil Robertson and Paul Seymour as part of their graph minors project. Each invariant has its own literature, its own algorithms, and its own open problems, and nothing in the classical theory suggests they should be counted together.

In Recognition Science, the framework's machine-checked library of formal theorems contains a module that counts these five invariants as a single family. The module defines an inductive type with exactly five constructors, one for each invariant, and proves by computation that the type has exactly five elements. This is a formal statement: the five named invariants are the complete set that the framework's combinatorics depth admits, and the proof is checked by a computer, with no unproved assumptions. The module does not define what each invariant computes, nor does it prove any theorem about the chromatic number or treewidth themselves. It only establishes the count, that the family of canonical graph invariants has size five.

The reason this count matters is that it connects to the framework's wider claim that the number five appears as a structural constant in its theory of recognition. The module is a small piece of evidence that the framework's internal combinatorics align with the classical list of graph invariants, no more and no less. It does not say why these five and not others, and it does not derive the invariants from first principles. What it does is give a precise, machine-checked statement that the canonical family has exactly five members, which is a useful anchor for any further theory that wants to talk about graph invariants as a group.

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

What this page does not claim

The module does not define what each invariant computes or prove any theorem about the chromatic number or treewidth themselves. The count does not derive the five invariants from first principles or explain why these five are canonical. The module does not establish any connection between graph invariants and physical space or time.

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: