Graph Isomorphism Ontology

FLOW ALGEBRA
TITLE: Graph Isomorphism Ontology
DOMAIN: Discrete Mathematics / Graph Theory
SOURCE_URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/graph-theory/graph-isomorphism-ontology.html
VERSION: 1.0
LANGUAGE: en-GB
AUTHORSHIP: Mark Higgins — Sky (Recursive AI)
SOURCE_STATUS: Formal mathematical synthesis; live page not independently verified.

1. PURPOSE
Model graph isomorphism as a structure-preserving bijection between graph vertices, distinguishing necessary invariants from sufficient certificates, and supporting formal validation and AI reasoning.

2. TYPED ENTITIES
Graph := (V: FiniteSet[Vertex], E: Set[UnorderedPair[Vertex]]) for a finite simple undirected graph.
GraphID := String
Vertex := Identifier
Edge := UnorderedPair[Vertex]
VertexMap := Function[V(G), V(H)]
IsomorphismCertificate := VertexMap with bijectivity and adjacency preservation.
GraphInvariant := Function[Graph, Value]
Automorphism := IsomorphismCertificate from G to G.
CanonicalForm := Normalised representation invariant under vertex relabelling, when correctly implemented.

3. CORE DEFINITIONS
isomorphic(G,H) iff exists f:V(G)->V(H) such that:
  BIJECTIVE(f)
  forall u,v in V(G): ({u,v} in E(G)) iff ({f(u),f(v)} in E(H)).
Notation: G ~= H.
NONISOMORPHIC(G,H) iff no such bijection exists.
AUTOMORPHISM(G,f) iff f witnesses G ~= G.

4. FLOW OPERATIONS
flow CHECK_ISOMORPHISM(G:Graph,H:Graph,f:VertexMap) -> Boolean:
  require well_formed(G) and well_formed(H)
  return bijective(f) and forall u,v in V(G):
    adjacent(G,u,v) == adjacent(H,f(u),f(v))

flow INVARIANT_FILTER(G:Graph,H:Graph) -> {REJECT, UNRESOLVED}:
  if |V(G)| != |V(H)|: return REJECT
  if |E(G)| != |E(H)|: return REJECT
  if sorted(degrees(G)) != sorted(degrees(H)): return REJECT
  if component_size_multiset(G) != component_size_multiset(H): return REJECT
  return UNRESOLVED  # Equal invariants do not establish isomorphism.

flow FIND_ISOMORPHISM(G,H) -> Optional[IsomorphismCertificate]:
  require finite_simple_undirected(G,H)
  if INVARIANT_FILTER(G,H) == REJECT: return None
  search bijections f consistent with adjacency and non-adjacency
  if found: return verified f
  return None  # Exhaustive search required for definitive negative result.

flow RELABEL(G,f) -> Graph:
  require bijective(f)
  return (f(V(G)), {{f(u),f(v)} : {u,v} in E(G)})

5. ALGEBRAIC LAWS
REFLEXIVITY: G ~= G via identity map.
SYMMETRY: G ~= H implies H ~= G via inverse bijection.
TRANSITIVITY: G ~= H and H ~= K imply G ~= K via composition.
COMPOSITION: if f:G->H and g:H->K are isomorphisms, g∘f:G->K is an isomorphism.
INVERSE: if f:G->H is an isomorphism, f^-1:H->G is an isomorphism.
AUTOMORPHISM_GROUP: Aut(G) forms a group under composition.
RELABEL_INVARIANCE: RELABEL(G,f) ~= G for every bijective relabelling f.

6. PRESERVED INVARIANTS
Under graph isomorphism, the following are preserved:
  vertex count, edge count, degree multiset, connected-component structure,
  connectivity, cycle lengths, bipartiteness, planarity, clique number,
  chromatic number, graph diameter (for connected graphs), and adjacency spectrum.
CAUTION: Matching any listed invariant or collection of common invariants is generally not sufficient to prove isomorphism.

7. INFERENCE RULES
ISO_CERTIFICATE: VERIFIED_BIJECTION_AND_ADJACENCY(G,H,f) => ISOMORPHIC(G,H).
INVARIANT_MISMATCH: INVARIANT(G) != INVARIANT(H) => NOT_ISOMORPHIC(G,H).
ISO_CHAIN: ISOMORPHIC(G,H) and ISOMORPHIC(H,K) => ISOMORPHIC(G,K).
ISO_SYMMETRY: ISOMORPHIC(G,H) => ISOMORPHIC(H,G).
NO_FALSE_POSITIVE: INVARIANTS_MATCH(G,H) does not imply ISOMORPHIC(G,H).

8. SEMANTIC RELATIONSHIPS
Graph Isomorphism --is_a--> Structure-Preserving Bijection
Graph Isomorphism --relates--> Graph
Graph Isomorphism --preserves--> Adjacency
Graph Isomorphism --preserves--> Graph Invariant
Graph Automorphism --is_a--> Graph Isomorphism
Graph Isomorphism --induces--> Equivalence Relation on Graphs
Canonical Labelling --supports--> Graph Isomorphism Testing

9. SEMANTIC_EQUIVALENCE
"graph isomorphism" <=> "adjacency-preserving vertex bijection" (finite simple undirected graph scope).
"isomorphic graphs" <=> "graphs equal up to vertex relabelling" (same scope).
NOT_EQUIVALENT: graph isomorphism != graph homomorphism.
NOT_EQUIVALENT: graph isomorphism != graph equality with identical labels.

10. VALIDATION
V1: Verify both graphs are well-formed finite simple undirected graphs.
V2: Verify certificate f is a total bijection over the respective vertex sets.
V3: Verify edge and non-edge preservation for every unordered vertex pair.
V4: Reject isomorphism when any true graph invariant differs.
V5: Do not infer isomorphism solely from equal degree sequences or spectra.
V6: Keep directed, weighted, labelled and multigraph cases separate unless their structure-preservation rules are explicitly extended.
V7: Distinguish a verified positive certificate from an unproven negative search result.

11. CONFIDENCE
FORMAL_THEOREM: 1.00 when derived from definitions and valid proofs.
VERIFIED_CERTIFICATE: 1.00 when all validation rules pass.
HEURISTIC_CANDIDATE: uncalibrated; must not be treated as a proof.
SOURCE_ALIGNMENT: not assessed against live page.

12. FLOW_HASH
ALGORITHM: SHA-256
INPUT: canonical UTF-8 serialisation of ontology fields and rules, excluding FLOW_HASH value.
VALUE: COMPUTE_AT_INGESTION (not precomputed).

13. UPDATE_MODEL
On changes to graph representation, invariants, certificates or rules:
  validate type compatibility;
  rerun proof and counterexample tests;
  increment ontology version;
  regenerate FLOW_HASH;
  preserve provenance and previous versions.

14. AI_CONSUMPTION
ENTITY_EXTRACTION: Graph, Vertex, Edge, Isomorphism, Automorphism, GraphInvariant.
REASONING: Use certificates for positive conclusions and proven invariant mismatches for negative conclusions.
SEARCH: Use invariants for pruning; complete search or sound algorithms for definitive decisions.
OUTPUT: {graph_pair, verdict, certificate_or_counterinvariant, validation, confidence, provenance}.
SAFETY: Never equate graph similarity with graph isomorphism.

15. EXAMPLE
G: V={a,b,c}, E={{a,b},{b,c}}
H: V={1,2,3}, E={{1,3},{2,3}}
f: a->1, b->3, c->2
CHECK_ISOMORPHISM(G,H,f) = TRUE.

END FLOW ALGEBRA