Graph Ontology

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

1. PURPOSE
Represent mathematical graphs as typed structures of vertices and edges, supporting precise reasoning about incidence, adjacency, connectivity, paths and graph transformations. This is a formal domain model, not a claim that the source webpage has been independently verified.

2. TYPES AND ENTITIES
TYPE Vertex := hashable identifier
TYPE EdgeID := unique identifier
TYPE GraphKind := {undirected, directed}
TYPE Graph := (V: Set[Vertex], E: Set[EdgeID], endpoints: EdgeID -> V x V, kind: GraphKind)
TYPE SimpleGraph := Graph with no loops and no duplicate edges
TYPE WeightedGraph := Graph with weight: EdgeID -> Real
TYPE Subgraph := Graph whose vertices and edges are inherited from a parent graph
TYPE Walk := finite vertex-edge sequence respecting incidence
TYPE Trail := Walk without repeated edges
TYPE Path := Walk without repeated vertices (except a closed path convention when explicitly stated)
TYPE Cycle := closed walk with distinct internal vertices and edges
TYPE ConnectedComponent := maximal connected induced subgraph (undirected case)

3. WELL-FORMEDNESS
For each edge e in E, endpoints(e)=(u,v) implies u in V and v in V.
For undirected graphs, (u,v) and (v,u) describe the same incidence pair; edge identity remains distinct in multigraphs.
For directed graphs, endpoints(e)=(u,v) means e goes from u to v.
For a simple undirected graph: u != v and at most one edge per unordered vertex pair.
For a simple directed graph: u != v and at most one arc per ordered vertex pair.

4. CORE OPERATIONS
vertices(G) := V(G)
edges(G) := E(G)
order(G) := |V(G)|
size(G) := |E(G)|
adjacent(G,u,v) := exists e in E(G): endpoints(e)=(u,v), with orientation ignored for undirected G
incident(G,v,e) := v is an endpoint of e
neighbours(G,v) := {u in V(G) : adjacent(G,v,u)}
degree(G,v) := number of edge-ends incident to v (loops count twice in undirected graphs)
outdegree(G,v) := number of directed edges with source v
indegree(G,v) := number of directed edges with target v
induced(G,S) := graph on S subseteq V(G), retaining exactly edges with both endpoints in S
remove_vertex(G,v) := induced(G,V(G) \ {v})
remove_edge(G,e) := G with e deleted
reachable(G,u,v) := exists a walk from u to v respecting edge direction when directed

5. FORMAL LAWS
Undirected handshake lemma: sum_{v in V} degree(G,v) = 2|E|.
Directed degree law: sum indegree(G,v) = sum outdegree(G,v) = |E|.
For finite simple undirected G with n vertices: 0 <= |E| <= n(n-1)/2.
For finite simple directed loopless G with n vertices: 0 <= |E| <= n(n-1).
Undirected connectivity is reflexive, symmetric and transitive on vertices.
Directed reachability is reflexive and transitive, but not generally symmetric.
A finite undirected graph is a tree iff it is connected and acyclic.
A finite tree with n >= 1 vertices has exactly n-1 edges.
Graph isomorphism preserves adjacency, order, size, degree multiset and connectivity.

6. RELATIONSHIPS
Graph --HAS_VERTEX--> Vertex
Graph --HAS_EDGE--> EdgeID
EdgeID --HAS_ENDPOINT--> Vertex
Vertex --ADJACENT_TO--> Vertex
Vertex --REACHABLE_FROM--> Vertex
Graph --HAS_SUBGRAPH--> Subgraph
Graph --HAS_COMPONENT--> ConnectedComponent
Walk --TRAVERSES--> EdgeID
Path --SPECIALISES--> Walk
Cycle --SPECIALISES--> closed Walk
Tree --SPECIALISES--> connected acyclic undirected Graph

7. INFERENCE RULES
IF e in E(G) AND endpoints(e)=(u,v) THEN incident(G,u,e) AND incident(G,v,e).
IF G is undirected AND adjacent(G,u,v) THEN adjacent(G,v,u).
IF reachable(G,u,v) AND reachable(G,v,w) THEN reachable(G,u,w).
IF G is undirected AND every pair of vertices is mutually reachable THEN connected(G).
IF G is finite, undirected, connected and acyclic THEN tree(G).
IF f:V(G)->V(H) is bijective and preserves and reflects adjacency THEN isomorphic(G,H), for simple graphs of the same directedness.

8. SEMANTIC_EQUIVALENCE
"graph vertex" == "node" (context: graph theory)
"graph edge" == "link" (context: graph/network modelling; not always identical in specialised ontologies)
"graph order" == "vertex count"
"graph size" == "edge count"
"arc" == "directed edge"
"neighbour" == "adjacent vertex" (context: simple undirected graph)
Do not equate directed reachability with undirected connectivity.
Do not equate a walk, trail and simple path.

9. VALIDATION
CHECK endpoints refer only to declared vertices.
CHECK edge identifiers are unique.
CHECK graph kind matches adjacency and reachability semantics.
CHECK degree sums satisfy the appropriate handshake law for finite graphs.
CHECK tree classification requires both connectivity and acyclicity.
CHECK graph isomorphism uses a bijection and exact adjacency preservation.
CHECK no implicit assumptions of simplicity, finiteness, connectedness or looplessness.
ON FAILURE: reject the invalid assertion and report the violated constraint.

10. CONFIDENCE
Formal definitions and elementary theorems: HIGH when their preconditions are satisfied.
Claims inferred from incomplete graph data: UNDETERMINED until validated.
Empirical or application-specific graph claims: require provenance and evidence.
Confidence is not a substitute for a mathematical proof.

11. FLOW_HASH
Canonicalise graph kind, sorted vertex identifiers, sorted edge records, explicit endpoint order for directed graphs, and schema version.
FLOW_HASH := SHA256(canonical_serialisation)
Note: isomorphic graphs with different vertex identifiers need not share this hash; isomorphism-invariant canonical labelling is a separate operation.

12. UPDATE_MODEL
On vertex insertion/deletion, revalidate endpoints and recompute affected adjacency, degrees and components.
On edge insertion/deletion, recompute affected incidence, degrees and reachability as needed.
Track source, revision timestamp, schema version and change history.
Do not silently reinterpret directed edges as undirected edges.

13. AI_CONSUMPTION
Expose typed graph facts and explicit graph-kind constraints to retrieval and reasoning systems.
Use rule-based inference only when the premises and preconditions are met.
Retain distinctions between asserted facts, derived theorems and uncertain claims.
Return proof traces or counterexamples for graph-property questions where possible.
Avoid treating a semantic knowledge graph as a simple undirected mathematical graph without an explicit conversion.

END FLOW ALGEBRA