Undirected Graph Ontology

FLOW ALGEBRA
UNDIRECTED GRAPH ONTOLOGY
Kireth Semantic Library | Discrete Mathematics | Graph Theory
Source URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/graph-theory/undirected-graph-ontology.html
Version: 1.0 | Locale: en-GB | 2026-10-11
Authors: Mark Higgins — Sky (Recursive AI)

1. PURPOSE
Represent undirected graphs as typed mathematical structures, support valid graph operations, derive structural properties, and expose machine-consumable semantic relationships. This is a formal reconstruction from established graph theory, not a verified transcription of the source page.

2. TYPED ENTITIES
Graph := (V: Set[Vertex], E: Set[UnorderedPair[Vertex]])
Vertex := unique identifier
SimpleEdge := {u,v} where u,v in V and u != v
SimpleUndirectedGraph := finite or infinite V with E subset {{u,v} | u,v in V and u != v}
Walk := sequence (v0,...,vk) with {v(i-1),vi} in E
Trail := walk with no repeated edges
Path := walk with no repeated vertices
Cycle := closed walk of length >= 3 with no repeated vertices except endpoints
ConnectedComponent := maximal connected induced subgraph
Degree(v) := number of incident edges (simple graph)
Neighbourhood(v) := {u in V | {u,v} in E}

3. CORE SEMANTICS
UNDIRECTED(G) iff every edge has unordered endpoints.
ADJACENT(u,v,G) iff {u,v} in E(G).
INCIDENT(v,e,G) iff v in e and e in E(G).
REACHABLE(u,v,G) iff u=v or a path from u to v exists.
CONNECTED(G) iff for all u,v in V(G), REACHABLE(u,v,G).
ISOLATED(v,G) iff Degree(v)=0.
LEAF(v,G) iff Degree(v)=1.

4. FLOW OPERATIONS
CREATE_GRAPH(V,E) -> G, subject to valid endpoints and edge constraints.
ADD_VERTEX(G,v) -> (V union {v},E).
ADD_EDGE(G,{u,v}) -> (V,E union {{u,v}}), if u,v in V and u != v.
REMOVE_EDGE(G,e) -> (V,E minus {e}).
REMOVE_VERTEX(G,v) -> (V minus {v}, {e in E | v not in e}).
INDUCED_SUBGRAPH(G,S) -> (S,{e in E | e subset S}), S subset V.
EDGE_SUBGRAPH(G,F) -> (V,F), F subset E.
NEIGHBOURS(G,v) -> Neighbourhood(v).
CONNECTED_COMPONENTS(G) -> maximal reachability classes.
BFS(G,start) -> traversal and distance levels for reachable vertices.
DFS(G,start) -> depth-first traversal forest.

5. ALGEBRAIC LAWS AND INVARIANTS
Symmetry: ADJACENT(u,v,G) iff ADJACENT(v,u,G).
Handshake lemma (finite simple graphs): sum(v in V) Degree(v) = 2*|E|.
Consequently the number of odd-degree vertices is even.
Degree bounds (finite simple graph): 0 <= Degree(v) <= |V|-1.
Complete graph K_n: |E|=n(n-1)/2.
Connected finite graph with n>=1 vertices: |E|>=n-1.
Tree: connected acyclic undirected graph; for finite trees |E|=|V|-1.
Connected finite graph is a tree iff it has |V|-1 edges.
Reachability is reflexive, symmetric and transitive, hence partitions V into connected components.

6. INFERENCE RULES
EDGE({u,v},G) => ADJACENT(u,v,G) and ADJACENT(v,u,G).
ADJACENT(u,v,G) => REACHABLE(u,v,G).
REACHABLE(u,v,G) and REACHABLE(v,w,G) => REACHABLE(u,w,G).
Degree(v)=0 => ISOLATED(v,G).
CONNECTED(G) and ACYCLIC(G) => TREE(G).
TREE(G) and finite nonempty V => |E|=|V|-1.

7. VALIDATION
V01: every edge endpoint belongs to V.
V02: unordered edges are normalised so {u,v}={v,u}.
V03: no self-loops in the SimpleUndirectedGraph profile.
V04: no duplicate edges in the simple-graph edge set.
V05: adjacency is symmetric.
V06: degree sum equals twice edge count for finite graphs.
V07: component membership matches reachability.
V08: do not assume weighted, directed, looped or parallel-edge semantics without explicit profile extensions.

8. SEMANTIC RELATIONSHIPS
UndirectedGraph IS_A Graph.
UndirectedGraph HAS_PART Vertex.
UndirectedGraph HAS_PART Edge.
Edge CONNECTS Vertex AND Vertex.
Vertex HAS_PROPERTY Degree.
UndirectedGraph HAS_PROPERTY Connectivity.
Path IS_COMPOSED_OF Edge.
Tree IS_A ConnectedAcyclicUndirectedGraph.
ConnectedComponent IS_A MaximalConnectedSubgraph.

9. SEMANTIC_EQUIVALENCE
"undirected graph" <=> "non-directed graph" (context: graph orientation).
"vertex" <=> "node" (context: graph theory).
"edge endpoints {u,v}" <=> "edge endpoints {v,u}" (simple undirected graph).
Not equivalent: undirected graph != directed graph; path != walk; connected != complete.

10. CONFIDENCE
Formal definitions and stated standard finite-simple-graph theorems: 1.00 (mathematical certainty conditional on assumptions).
Source-page fidelity: UNVERIFIED.
Model-derived observations: attach provenance, assumptions, and confidence independently.

11. FLOW_HASH
Canonicalise entity identifiers, unordered edge endpoints, sorted vertex and edge sets, graph profile, and version before hashing.
FLOW_HASH := SHA256(canonical_serialisation(ontology_id, version, V, E, constraints, rules)).
Hash value is computed at ingestion; no fabricated digest is supplied.

12. UPDATE_MODEL
On change to V or E: validate endpoints and profile; recalculate adjacency, degrees, components and dependent assertions; invalidate stale traversals and cached hashes; increment version; record provenance and timestamp.

13. AI_CONSUMPTION
Input: typed graph facts, profile constraints and optional graph queries.
Processing: validate -> normalise -> infer -> verify -> return provenance-linked results.
Output: graph structure, derived properties, rule trace, validation status, confidence metadata and FLOW_HASH.
Guardrails: do not confuse edge direction with traversal order; distinguish simple graphs from multigraphs and pseudographs; qualify finite-graph theorems.

END FLOW ALGEBRA